[기하학] 선분 교차 3 (20149) (C++)

 

https://www.acmicpc.net/problem/20149

20149번: 선분 교차 3

 

 

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");
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!