[기하학] 선분 교차 3 (20149) (C++)
https://www.acmicpc.net/problem/20149
20149번: 선분 교차 3
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
www.acmicpc.net
1. 문제 개요
2차원 좌표 평면 위의 두 선분의 양 끝점이 주어졌을 때, 두 선분이 교차하는지 아닌지 구하는 문제.
선분 교차 2 문제와 같지만 선분이 한 점에서 만나는 경우 점의 좌표를 출력하는 문제.
2. 입출력
3. 문제 풀이
선분 교차 1 문제와 같이 점 3개의 방향성을 나타내는 CCW 알고리즘을 사용하여 풀이 할 수 있다.
CCW 알고리즘은 세 점으로 아루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구하는 알고리즘이다.
세 개의 점이 시계 방향, 반시계 방향 또는 평행하게 놓여있는지 여부를 알 수 있다.
typedef struct {
long long x, y;
}pii;
long long ccw(pii a, pii b, pii c)
{
long long ans = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
if (ans < 0) return 1;
else if (ans > 0) return -1;
else return 0;
}
ans > 0: 반시계 방향
ans = 0: 일직선
ans < 0: 시계 방향
여기에 더해서 세 개 이상의 점이 나란히 있는 경우를 고려해야한다. 이 경우는 ccw 값이 0이 되는 경우인데, ccw만 가지고는 해결할 수 없기 때문에 case를 나누어서 문제를 풀면된다.
밑의 그림에서 ccw 값이 0이 되는 경우는 그림2, 그림3, 그림4, 그림6, 그림7이며 좌표를 구할 수 있는 경우는 그림1, 그림2, 그림3, 그림6이다. 그림4와 같은 경우에는 선분끼리 만나는 점이 무수히 많으므로 좌표를 구할 수 없다.
그림1과 같은 경우에는 선분의 교점을 구하는 식으로 교점을 구할 수 있다.
여기서 주의해야할점은 선분의 기울기가 무한대가 되는 경우이다. 이 경우는 A, B 또는 C, D의 x 값이 같을 때이므로 따로 케이스를 분리해서 해결하면 된다.
if((ABC*ABD<0)&&(CDA*CDB<0))
{ // 세 점이 한 선분 위에 있지 않으며 교차하는 경우
long double a,b,c,d;
long double interX, interY;
if(A.x==B.x){
interX = A.x;
interY = (D.y-C.y)*(interX-C.x)/(D.x-C.x)+C.y;
} else if(C.x==D.x){
interX = C.x;
interY = (B.y-A.y)*(interX-A.x)/(B.x-A.x)+A.y;
} else {
a = ((long double)(B.y-A.y))/(B.x-A.x);
b = ((long double)(B.x*A.y-A.x*B.y))/(B.x-A.x);
c = ((long double)(D.y-C.y))/(D.x-C.x);
d = ((long double)(D.x*C.y-C.x*D.y))/(D.x-C.x);
interX = (b-d)/(c-a);
interY = a*(b-d)/(c-a) + b;
}
printf("1\n%.20Lf %.20Lf\n",interX,interY);
}
그림2, 그림3, 그림6 같은 경우에는 두 선분의 양쪽 끝점 중 한가지가 선분끼리 만나는 점의 좌표가 되므로 케이스를 나누어서 좌표값을 구하였다.
else if(ABC*ABD*CDA*CDB==0) // 세 점 또는 네 점이 한 선분 위에 있는 경우
{
if(ABC*ABD<0||CDA*CDB<0) { // 그림 2
if(CDA==0)
printf("1\n%lld %lld\n",A.x,A.y);
else if(CDB==0)
printf("1\n%lld %lld\n",B.x,B.y);
else if(ABC==0)
printf("1\n%lld %lld\n",C.x,C.y);
else if(ABD==0)
printf("1\n%lld %lld\n",D.x,D.y);
}
else if((ABC==0&&ABD==0)||(CDA==0&&CDB==0)) // 네 점이 한 선분 위에 있는 경우
{
if((Dis(B, C)==0&&Dis(A,D)>Dis(C,D))||(Dis(B, C)==0&&Dis(A,D)>=Dis(C,D)))
printf("1\n%lld %lld\n",B.x,B.y); // 그림 3
else if((Dis(A, C)==0&&Dis(B,D)>Dis(A,B))||(Dis(A, D)==0&&Dis(B,C)>Dis(A,B)))
printf("1\n%lld %lld\n",A.x,A.y); // 그림 3
else if(max(Dis(A,C),Dis(B,C))<=Dis(A,B)||max(Dis(A,D),Dis(B,D))<=Dis(A,B))
printf("1\n"); // 그림 4
else if(max(Dis(C,A),Dis(D,A)) <= Dis(C,D)||max(Dis(C,B),Dis(D,B)) <= Dis(C,D))
printf("1\n"); // 그림 4
else
printf("0\n"); // 그림 5
}
else if(Dis(B, C)*Dis(B, D)==0) // 그림 6
printf("1\n%lld %lld\n",B.x,B.y);
else if(Dis(A, C)*Dis(A, D)==0) // 그림 6
printf("1\n%lld %lld\n",A.x,A.y);
else
printf("0\n"); // 그림 7
}
4. 전체 코드
#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
//선분 교차1
typedef struct {
long long x, y;
}pii;
long long Dis(pii a, pii b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
long long ccw(pii a, pii b, pii c)
{
long long ans = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
if (ans < 0) return 1;
else if (ans > 0) return -1;
else return 0;
}
int main(void)
{
pii A, B, C, D;
scanf("%lld%lld%lld%lld",&A.x,&A.y,&B.x,&B.y);
scanf("%lld%lld%lld%lld",&C.x,&C.y,&D.x,&D.y);
long long ABC = ccw(A, B, C);
long long ABD = ccw(A, B, D);
long long CDA = ccw(C, D, A);
long long CDB = ccw(C, D, B);
if((ABC*ABD<0)&&(CDA*CDB<0)) // 그림 1
{ // 세 점이 한 선분 위에 있지 않으며 교차하는 경우
long double a,b,c,d;
long double interX, interY;
if(A.x==B.x){
interX = A.x;
interY = (D.y-C.y)*(interX-C.x)/(D.x-C.x)+C.y;
} else if(C.x==D.x){
interX = C.x;
interY = (B.y-A.y)*(interX-A.x)/(B.x-A.x)+A.y;
} else {
a = ((long double)(B.y-A.y))/(B.x-A.x);
b = ((long double)(B.x*A.y-A.x*B.y))/(B.x-A.x);
c = ((long double)(D.y-C.y))/(D.x-C.x);
d = ((long double)(D.x*C.y-C.x*D.y))/(D.x-C.x);
interX = (b-d)/(c-a);
interY = a*(b-d)/(c-a) + b;
}
printf("1\n%.20Lf %.20Lf\n",interX,interY);
}
else if(ABC*ABD*CDA*CDB==0) // 세 점 또는 네 점이 한 선분 위에 있는 경우
{
if(ABC*ABD<0||CDA*CDB<0) { // 그림 2
if(CDA==0)
printf("1\n%lld %lld\n",A.x,A.y);
else if(CDB==0)
printf("1\n%lld %lld\n",B.x,B.y);
else if(ABC==0)
printf("1\n%lld %lld\n",C.x,C.y);
else if(ABD==0)
printf("1\n%lld %lld\n",D.x,D.y);
}
else if((ABC==0&&ABD==0)||(CDA==0&&CDB==0)) // 네 점이 한 선분 위에 있는 경우
{
if((Dis(B, C)==0&&Dis(A,D)>Dis(C,D))||(Dis(B, C)==0&&Dis(A,D)>=Dis(C,D)))
printf("1\n%lld %lld\n",B.x,B.y); // 그림 3
else if((Dis(A, C)==0&&Dis(B,D)>Dis(A,B))||(Dis(A, D)==0&&Dis(B,C)>Dis(A,B)))
printf("1\n%lld %lld\n",A.x,A.y); // 그림 3
else if(max(Dis(A,C),Dis(B,C))<=Dis(A,B)||max(Dis(A,D),Dis(B,D))<=Dis(A,B))
printf("1\n"); // 그림 4
else if(max(Dis(C,A),Dis(D,A)) <= Dis(C,D)||max(Dis(C,B),Dis(D,B)) <= Dis(C,D))
printf("1\n"); // 그림 4
else
printf("0\n"); // 그림 5
}
else if(Dis(B, C)*Dis(B, D)==0) // 그림 6
printf("1\n%lld %lld\n",B.x,B.y);
else if(Dis(A, C)*Dis(A, D)==0) // 그림 6
printf("1\n%lld %lld\n",A.x,A.y);
else
printf("0\n"); // 그림 7
}
else
printf("0\n");
}
아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!