[PS] 백준 10255번: 교차점

|

문제

내가 이해한 문제 내용

축에 평행한 직사각형과 하나의 선분에 대한 좌표가 주어질 때 교차점의 개수를 구하여라.

접근 방식

처음에 접근할 때 직선의 방정식을 계산한 뒤 교점을 구하는 방식으로 했는데 한 3~4시간을 썼는데도 안돼는 케이스가 상당히 많아서 풀이를 보게 되었다.

어려웠던 점 & 배운 점

풀이를 이해하는데도 상당히 오랜 시간이 걸렸다. 벡터의 외적을 이용하는 CCW를 사용해서 선분과 직사각형과의 변에 대한 교차점을 확인하는 방식이었다. 잊지 않기 위해 확실히 정리하고자 한다.

먼저 벡터의 외적에 대한 정의를 알아야 한다. 벡터 A와 벡터 B를 외적해서 얻을 수 있는 결과는 벡터 B가 벡터 A를 기준으로 어느 방향으로, 어느 정도 회전했는지를 알 수 있는 척도로 말할 수 있다.

위 그림과 같이 벡터 A와 벡터 B가 이루는 각이 $\theta_1$일 때 $A\times B = OAOBsin\theta_1$으로 정의된다. ($OA,OB$는 각각 벡터의 길이이다.) 외적의 의미에 따라 벡터 B는 A로부터 $\theta_1$만틈 시계방향으로 회전한 상태이며 벡터 C는 $A$로부터 $\theta_2$만큼 반시계방향으로 회전한 상태이다. 그럼 이걸 어떻게 활용할 수 있을까?

$sin(-\theta)=-sin\theta$에 따라서 시계방향이면 외적의 값이 음수이고 반시계방향이면 양수라는 것을 알 수 있다. 이걸통해서 CCW(Counter ClockWise)를 판단할 수 있다. 즉, 방향성을 판단하는 것이다.

문제에선 직사각형이 주어지기 때문에 좌표 4개가 주어진다고 볼 수 있다. 이 때 주어지는 선분과의 교차점 여부를 판단하는데 CCW를 사용하는 것이다. CCW를 어떻게 사용할 수 있을까? CCW에 따라 선분의 교차점을 계산할때는 3가지 경우를 볼 수 있다.

위에서 교점이 무한대인 경우는 일직선에 놓이는 경우를 말한다. 이제 점 3개를 잡고 CCW를 판단하여 선분의 교차점을 얻어내보자.

먼저 교점이 0개일 때는 점 3개를 A,B,C로 잡았을 때 반시계방향인 것과 A,B,D로 잡았을 때도 반시계방향인 것을 알 수 있다. 이렇게 2개의 선분에 대해 서로 CCW를 계산했는데 같은 방향이 하나라도 있는 경우에는 교점이 0개이게 된다. 위 경우에 점 3개를 D,C,A나 D,C,B로 잡으면 다른 방향이 되지만 역으로 계산했을 때 같은 방향이 있기 때문에 교점이 0개가 되는 것이다. 따라서, 교점이 1개인 경우는 둘 다 다른 방향이 성립해야 한다.

3개의 점을 어떻게 잡으나 위의 경우는 다른 방향이 성립함을 알 수 있다. 따라서 2개의 선분이 교차함을 확인할 수 있다. 이제 마지막으로 일직선에 있는 경우인데 굳이 그림으로 볼 필요도 없는게, 3개의 점이 일직선에 있으면 $\theta=0$이라는 것이므로 그 값도 0이라는 것을 알 수 있다.

결론적으로 아래와 같이 판단할 수 있게 된다.

  • 2개의 선분이 서로에 대한 벡터의 외적값 부호가 반대이면 교점이 1개 존재한다.
  • 2개의 선분이 서로에 대한 벡터의 외적값 부호가 하나라도 동일하면 교점이 존재하지 않는다.
  • 벡터의 외적값이 0이라면 일직선 상에 놓여있으므로 교점이 무한대만큼 존재한다.

거의 다 왔다. 이제 이걸 이용해서 직사각형의 각 변을 보면 된다. 아래 그림과 같은 방식으로 보면 된다.

4개의 변에 대해 CCW를 통해 교점을 구하면서 더해주면 된다. 단, 주의할 점은 선분의 끝이 직사각형의 꼭짓점에 해당하는 경우는 중복계산되기 때문에 그 경우엔 1을 빼주어야 한다. 이 방법은 4개의 꼭짓점을 돌아가면서 기존 선분과의 교차여부를 검사해주면 된다.

그렇게 여기까지 해서 풀이를 이해하고 코드를 공부하면서 풀었지만 자꾸 100%에서 틀렸다고 해서 뭐가 문젠지 보니까 선분과 직사각형의 변이 일직선 상에 놓일 때가 실수였다. 어느 방향에서라도 ccw 값이 0이 나올 경우는 반드시 한 점에서 만나게 되어있다. 그러나 그것이 일직선에 완전히 놓일 경우에는 3가지 경우가 존재한다.

  • 아예 겹치지 않는 경우(0)
  • 한 점만 겹치는 경우(1)
  • 한 선분이 다른 선분에 완전히 포함되는 경우(무한대)

따라서 위 경우를 반드시 고려해주어야 맞을 수가 있다.

외적을 계산할 때 이 문제에선 좌표로 계산하는데 벡터 A의 좌표를 $(x_a,y_a)$라고 하고 벡터 B의 좌표를 $(x_b,y_b)$라고 하면 외적은 $x_ay_b-y_ax_b$로 정의된다.

시간복잡도

입력에 따라서 반복하는 경우가 없고 벡터의 외적이나 CCW, 또는 교점 판단 모두 상수시간이 걸리는데다 직사각형의 4개 변만 반복해서 계산하므로 $O(1)$이라고 생각한다.

코드

#include <cstdio>
#include <algorithm>

int tc,xmin,ymin,xmax,ymax,x1,y1,x2,y2;

struct Point{
    int x;
    int y;

    bool operator==(const Point& p) const{
        return x==p.x && y==p.y;
    }

    bool operator<(const Point& p) const{
        if(x!=p.x) return x<p.x;
        else return y<p.y;
    }
};

Point a,b;
Point left_bottom,right_bottom,left_top,right_top;

inline int cross_product(Point a, Point b){
    return a.x*b.y-a.y*b.x;
}

int ccw(Point a, Point b, Point c){
    Point a_b = {b.x-a.x,b.y-a.y};
    Point a_c = {c.x-a.x,c.y-a.y};
    return cross_product(a_b,a_c);
}

int intersect_num(Point dir1, Point dir2){
    int ccw1 = ccw(a,b,dir1), ccw2 = ccw(a,b,dir2);
    int ccw3 = ccw(dir1,dir2,a), ccw4 = ccw(dir1,dir2,b);

    if(!ccw1 && !ccw2){

        if(b<a) std::swap(a,b);
        if(dir2<dir1) std::swap(dir1,dir2);

        if(ccw1==0&&ccw2==0&&ccw3==0&&ccw4==0){
            if(b<dir1 || dir2<a) return 0;
            if(b==dir1 || dir2==a) return 1;
            return -1;
        }
        return 1;
    }

    if((ccw1>0&&ccw2>0) || (ccw3>0&&ccw4>0) || (ccw1<0&&ccw2<0) || (ccw3<0&&ccw4<0)) return 0;
    else return 1;
}

int main(void)
{
    scanf("%d",&tc);

    while(tc--){
        scanf("%d%d%d%d",&xmin,&ymin,&xmax,&ymax);
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        a = {x1,y1};
        b = {x2,y2};
        
        left_bottom = {xmin,ymin};
        right_bottom = {xmax,ymin};
        left_top = {xmin,ymax};
        right_top = {xmax,ymax};

        Point p[4][2] = {
            {left_bottom,left_top},
            {right_bottom,left_bottom},
            {left_top,right_top},
            {right_top,right_bottom}
        };

        int ans = 0,i;
        for(i=0; i<4; i++){
            int inter = intersect_num(p[i][0],p[i][1]);
            if(inter==-1) break;
            ans += inter;
            if(intersect_num(p[i][0],p[i][0])) ans--;
        }
        printf("%d\n",i<4?4:ans);
    }
    return 0;
}