[백준] 17386번 선분 교차 1

 

 

문제

소스코드

#include<iostream>
 
using ll = long long;
struct Point {
    ll x;
    ll y;
};
 
ll CCW(Point A, Point B, Point C) {
    ll result = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
 
    if (result > 0) {
        return 1;
    }
    else if (result < 0) {
        return -1;
    }
    return 0;
}
 
int main() {
    Point A, B, C, D;
 
    //L1== AB
    //L2== CD
    std::cin >> A.x >> A.y >> B.x >> B.y;
    std::cin >> C.x >> C.y >> D.x >> D.y;
 
    ll ABC = CCW(A, B, C);
    ll ABD = CCW(A, B, D);
    ll CDA = CCW(C, D, A);
    ll CDB = CCW(C, D, B);
 
 
    if ((ABC * ABD) == 0 && (CDA * CDB) == 0) {
        ll a, b, c, d;
        a = A.x;
        b = B.x;
        c = C.x;
        d = D.x;
        //B---A
        if (B.x < A.x) {
            a = B.x;
            b = A.x;
        }
        //D---C
        if (D.x < C.x) {
            c = D.x;
            d = C.x;
        }
        if (a <= d && c <= d)
            std::cout << "1\n";
        else
            std::cout << "0\n";
    }
    else if ((ABC * ABD) <= 0 && (CDA * CDB) <= 0) {
        std::cout << "1\n";
    }
    else {
        std::cout << "0\n";
    }
}
 

 

후기

 

이 문제를 해결하기 위한 키워드는 CCW이다.

CCW 알고리즘을 사용하면 선분이 겹쳐있는지 알 수 있다. 

이렇게 선분 AB와 선분 CD가 있을 때 선분 AB를 기준으로 CCW(A,B,C) 와 CCW(A,B,D)를 진행하면 하나는 시계 방향 하나는 반 시계 방향이 나오기 때문에 교차여부를 확인할 수 있다.  하지만 이러한 방법도 한계가 존재한다.

바로 위와 같은 경우이다. 이 경우에는 서로 교차하지 않지만 CCW(A,B,C)와 CCW(A,B,D)를 진행하면 시계와 반시계 방향이기 나오기 때문에 교차판정이 나오게 된다. 이것을 해결하는 방법은 비교적 어렵지 않다. CCW(A,B,C) 와 CCW(A,B,D)를 진행한거와 동일하게 CD에도 CCW(C,D,A) CCW(C,D,B)연산을 진행하는 것이다.

이렇게 진행 후 CCW(A,B,C)* CCW(A,B,D) 와 CCW(C,D,A)*CCW(C,D,B)를 곱한 후 두개가 모두 0보다 같거나 작을 경우가 교차를 하는 경우이다.

    ll ABC = CCW(A, B, C);
    ll ABD = CCW(A, B, D);
    ll CDA = CCW(C, D, A);
    ll CDB = CCW(C, D, B);

 

이렇게 진행을 하여도 한개의 반례 사례가 존재한다.

이 경우에는 아래는 교차하고 위는 교차하지 않지만 둘다 0이 나오기 때문에 따로 비교 판단을 진행해야 한다.

if ((ABC * ABD) == 0 && (CDA * CDB) == 0) {
        ll a, b, c, d;
        a = A.x;
        b = B.x;
        c = C.x;
        d = D.x;
        //B---A
        if (B.x < A.x) {
            a = B.x;
            b = A.x;
        }
        //D---C
        if (D.x < C.x) {
            c = D.x;
            d = C.x;
        }
        if (a <= d && c <= d)
            std::cout << "1\n";
        else
            std::cout << "0\n";
    }

이 코드가 바로 해당 반례를 진행한 코드이다.

중간에 값을 바꾸는 코드가 있는대 이 코드는 위와 같이 항상 A가 B보다 왼쪽에 있다는 보장이 없기 때문에 아래와 같은 경우를 처리하기 위한 코드이다. 

 

문제를 진행하면서 도움이 되는 좌표찍기 웹사이트(그래픽 계산기) 링크를 첨부한다.

 

출처 및 레퍼런스

문제 링크: https://www.acmicpc.net/problem/17386

그래픽 계산기 링크: https://www.geogebra.org/graphing 

그림: 본인

 

관련 글

[자료구조 알고리즘/기타 알고리즘(Other)] - CCW(Counter Clock Wise)

[온라인 코딩/수학(Math)] - [백준] 11758번 CCW