https://www.acmicpc.net/problem/17387
17387번: 선분 교차 2
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
www.acmicpc.net
문제설명
바로 전 게시글인 17386번 선분 교차1 문제에 선분의 끝 부분이 닿아있는것도 교차하는것으로 보는 조건이 더 붙었다.
이 단순 조건 하나가 더 붙어서 예외 처리할게 너무 많아져서 훨씬 어려워진 느낌을 받았음..
4개의점을 p1(x1,y1) p2(x2,y2) p3(x3,y3) p4(x4,y4)로 정의하였다.
4개점의 x좌표가 전부 같을 때 즉 선분 두개가 y축에 평행한 경우에 y1 y2 사이에 y3 y4 둘중하나만 있으면 교차하는것이므로 1을 출력하고 종료 그렇지 않다면 0을 출력하고 종료했다.
그리고 ccw를 사용해서 4개의 점이 전부 가상의 한 직선에 있을경우와 그렇지 않은경우로 나눴고
4개 점이 가상의 한 직선에 있는경우엔 각 점의 x좌표에 따라 닿는지 여부를 판단하여 닿으면 1을 그렇지 않다면 0을 출력했다.
여기서 delta_x delta_y라는 변수를 두었는데 이건 x증분 y증분을 의미하고 기약 분수형태로 뽑아내기위해 gcd함수를 사용하고 현재 x 값과 y값에 x증분 y증분을 더 해가다가 다른쪽 선분의 x,y좌표와 일치하면 접하는것으로 판단을하고 1을 출력하고 종료했다.
끝날때까지 다른쪽 선분의 x,y좌표가 일치하는것이없었으면 접하지 않는것으로 판단을 하고 0을 출력하고 종료했다.
그림으로 보면 이해가 더 쉬울 것 같아서 대충 그려보았는데 위 아래 둘다 가상의 한직선 위에 존재하는 점이지만
위 그림은 A내에서 x1,y1에서 시작해서 delta_x delta_y를 더 해가며 x2,y2를 만날때까지 반복을 하는데 x2,y2를 만나기 전에 x3,y3을 만나기 때문에 교차하는 것으로 본다.
반대로 아래 그림에선 x1,y1에서 x2,y2까지 만날때까지 x3,y3이나 x4,y4를 만나지 않기 때문에 교차하지 않는걸로 본다.
왜 delta_x delta_y로 생각을했냐면 입력으로 주어지는 4개의 점의 좌표는 정수이기 때문에 이렇게 해도 풀린다.
만약 정수가아닌 실수가 주어졌으면 이 방법은 못써먹는다.
4개 점이 가상의 한직선에 있지 않은 경우엔 선분교차 1의 코드를 베껴와 살짝 수정해주었다.
코드
#include <iostream>
#include <algorithm>
#include <cmath>
typedef long long int ll;
using namespace std;
ll ccw(ll x1,ll x2,ll x3,ll y1,ll y2,ll y3);
ll gcd(ll n,ll m);
int main(){
cout.tie(NULL);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
ll x[4];
ll y[4];
for(ll i=0; i<4; i++)
{
cin>>x[i]>>y[i];
}
if(x[0]==x[1]&&x[0]==x[2]&&x[0]==x[3])
{
if((min(y[0],y[1])<=y[2]&&y[2]<=max(y[0],y[1]))||(min(y[0],y[1])<=y[3]&&y[3]<=max(y[0],y[1])))
{
cout<<1;
return 0;
}
else
{
cout<<0;
return 0;
}
}
ll a=ccw(x[0],x[1],x[2],y[0],y[1],y[2]);
ll b=ccw(x[0],x[1],x[3],y[0],y[1],y[3]);
ll c=ccw(x[2],x[3],x[0],y[2],y[3],y[0]);
ll d=ccw(x[2],x[3],x[1],y[2],y[3],y[1]);
if(a==0&&b==0&&c==0&&d==0)
{
ll delta_x;
ll delta_y;
if(min(x[0],x[1])<min(x[2],x[3]))
{
if(x[0]>x[1])
{
delta_x=x[0]-x[1];
delta_y=y[0]-y[1];
ll g=gcd(abs(delta_x),abs(delta_y));
delta_x=delta_x/g;
delta_y=delta_y/g;
ll cx=x[1];
ll cy=y[1];
while(1)
{
if((cx==x[2]&&cy==y[2])||(cx==x[3]&&cy==y[3]))
{
cout<<1;
return 0;
}
if(cx==x[0]&&cy==y[0])
{
cout<<0;
return 0;
}
cx=cx+delta_x;
cy=cy+delta_y;
}
}
else if(x[1]>x[0])
{
delta_x=x[1]-x[0];
delta_y=y[1]-y[0];
ll g=gcd(abs(delta_x),abs(delta_y));
delta_x=delta_x/g;
delta_y=delta_y/g;
ll cx=x[0];
ll cy=y[0];
while(1)
{
if((cx==x[2]&&cy==y[2])||(cx==x[3]&&cy==y[3]))
{
cout<<1;
return 0;
}
if(cx==x[1]&&cy==y[1])
{
cout<<0;
return 0;
}
cx=cx+delta_x;
cy=cy+delta_y;
}
}
}
else
{
if(x[2]>x[3])
{
delta_x=x[2]-x[3];
delta_y=y[2]-y[3];
ll g=gcd(abs(delta_x),abs(delta_y));
delta_x=delta_x/g;
delta_y=delta_y/g;
ll cx=x[3];
ll cy=y[3];
while(1)
{
if((cx==x[0]&&cy==y[0])||(cx==x[1]&&cy==y[1]))
{
cout<<1;
return 0;
}
if(cx==x[2]&&cy==y[2])
{
cout<<0;
return 0;
}
cx=cx+delta_x;
cy=cy+delta_y;
}
}
else if(x[3]>x[2])
{
delta_x=x[3]-x[2];
delta_y=y[3]-y[2];
ll g=gcd(abs(delta_x),abs(delta_y));
delta_x=delta_x/g;
delta_y=delta_y/g;
ll cx=x[2];
ll cy=y[2];
while(1)
{
if((cx==x[0]&&cy==y[0])||(cx==x[1]&&cy==y[1]))
{
cout<<1;
return 0;
}
if(cx==x[3]&&cy==y[3])
{
cout<<0;
return 0;
}
cx=cx+delta_x;
cy=cy+delta_y;
}
}
}
}
else
{
if(a!=b)
{
if(c!=d)
{
cout<<1;
}
else
{
cout<<0;
}
}
else
{
cout<<0;
}
return 0;
}
return 0;
}
ll ccw(ll x1,ll x2,ll x3,ll y1,ll y2,ll y3){
if(x1==x2)
{
if(x3>x1)
{
return -1;
}
else if(x3<x1)
{
return 1;
}
}
else if(x1==x3)
{
if(y3<y1)
{
return -1;
}
else if(y3>y1)
{
return 1;
}
}
else
{
ll a=(x1-x3)*(y1-y2);
ll b=(x1-x2)*(y1-y3);
if(a<b)
{
return 1;
}
else if(a>b)
{
return -1;
}
}
return 0;
}
ll gcd(ll n,ll m){
if(n>m)
{
ll tmp=m;
m=n;
n=tmp;
}
if(n==0)
{
return m;
}
else
{
return gcd(m%n,n);
}
}
'백준문제풀이' 카테고리의 다른 글
| 백준 문제 1005번 ACM Craft 문제풀이 c++ (0) | 2022.03.13 |
|---|---|
| 백준 문제 1002번 터렛 문제풀이 c++ (0) | 2022.03.13 |
| 백준 문제 17386번 선분 교차 1 문제풀이 c++ (0) | 2022.03.13 |
| 백준 문제 11758번 CCW 문제풀이 c++ (0) | 2022.03.13 |
| 백준 문제 1041번 주사위 문제풀이 c++ (0) | 2022.03.07 |