백준 10255 교차점 C++

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

케이스 처리를 어떤 순서로 하는지가 중요하고, 예외 처리를 꼼꼼하게 하는 것이 중요한 문제이다.

기본적으로, 교점이 존재하지 않을 때를 먼저 없애준다. 교점이 없으면 나머지 모든 케이스를 볼 필요가 없으니까.

비슷한 맥락으로 다음으로 교점이 무수히 많은 경우를 처리해준다.

그리고 경우를 나눠서, 선분이 사각형의 꼭지점을 지나는 경우와 그렇지 않은 경우로 나눠서 진행한다.

1. 교점이 없는지 판단하는 것은, 기본적인 예외처리가 포함된 템플릿을 활용한다. CCW 곱을 연산한 결과가 모두 0보다 작거나 같고, 사각형의 내부에 선분이 존재하지 않는다면 만난다고 판단한다.

한 번이라도 만나게 되면 교점이 존재한다고 판단하고 스킵하면 된다.

2. 교점이 무수히 많은지 판단은, 직관적으로 하드코딩 했다. 기본적인 정렬은 x좌표가 작은 점이 선분의 시작점으로 오게 했다. 하지만 y좌표에 대해서는 정렬을 하지 않았기 때문에 (당연히 x좌표 혹은 y좌표 둘 중 하나로 밖에 정렬할 수 없다) y좌표는 어떤 크기 관계를 가지는지 알 수 없다.

따라서 직사각형의 각 변위에 그대로 선분이 놓이는 경우를 모두 따져주면 된다.

3. 선분이 사각형의 꼭짓점을 지나는 경우

이런 상황이면, 선분의 두 점을 A,B 그리고 사각형의 두 점을 C, D라고 했을때, 선분이 C를 지나간다면 CCW(A,B,C) = 0 일 것이고, 선분이 D를 지난다면 CCW(A,B,D) = 0 일 것이다.

즉 선분이 사각형의 꼭짓점을 지나는 경우는, 선분을 기준으로 사각형의 변을 CCW 했을 때 무조건 0이 나오게 된다.

따라서 함수를 구현할 때, CCW(A,B,C) * CCW(A,B,D) == 0 and CCW(C,D,A) * CCW(C,D,B) <= 0  이를 만족하면 선분 AB가 꼭짓점 C혹은 D를 지나는 경우이다. 이 때 카운트를 하게 되면, CD 인 경우와 선분 EC인 경우에도 중복으로 카운트가 될 것이기 때문에 (C를 AB가 지난다고 할 경우) 최종 카운트 횟수를 2로 나눠준다.

4. 선분이 사각형의 변을 지나는 경우

CCW(A,B,C) & CCW(A,B,D) < 0 and CCW(C,D,A) * CCW(C,D,B) <= 0 이 상황이다. 앞의 부등식이 0이게 되면 위에서 봤듯이 꼭짓점을 지나는 경우이다.

추가적으로 사각형의 변을 기준으로 하는 CCW가 그대로 <= 이어도 괜찮은 이유는, 가령 사각형의 변 CD위에 선분 AB의 끝점 A가 위치해 있는 경우 CCW(C,D,A)가 0이 된다. 이 경우는 특별한 경우가 아니고 그냥 CD와 AB가 한 점에서 만난다는 조건일 뿐이다. 따라서 고려해 줄 필요가 없다. 0이 들어가고 안 들어가고를 신경쓸 필요도 없고 말이다.

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
struct POS {
    int x, y;
};
vector<int> ans;
set<pair<int, int> > chk;
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    ll ret = (x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1);
    if (ret > 0) return 1;
    else if (ret < 0) return -1;
    else 
        return 0; 
}
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    //ccw곱 음수 + 사각형 내부 피하면 교차
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        if ((x1 < x3 && x1 < x4 && x2 < x3 && x2 < x4) ||
            (x3 < x1 && x3 < x2 && x4 < x1 && x4 < x2)) return false;
        if ((y1 < y3 && y1 < y4 && y2 < y3 && y2 < y4) ||
            (y3 < y1 && y3 < y2 && y4 < y1 && y4 < y2)) return false;
        return true;
    }
    return false;
}
bool isCross_rect_point(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    int line = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
    int rect = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);
    if (line == 0 && rect <= 0) return true;
    else return false;
}
bool isCross_rect_line(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    int line = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4);
    int rect = ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2);
    if (line < 0 && rect <= 0) return true;
    else return false;
}
 
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        int xmin, ymin, xmax, ymax;
        cin >> xmin >> ymin >> xmax >> ymax;
        POS r1 = { xmin, ymin };
        POS r2 = { xmin, ymax };
        POS r3 = { xmax, ymin };
        POS r4 = { xmax, ymax };
 
        POS l1, l2;
        int x1, y1, x2, y2;
        cin >> l1.x >> l1.y >> l2.x >> l2.y;
        if (l1.x > l2.x) swap(l1, l2);
 
        //1. 교점 없음
        bool isNone = true;
        if (isCross(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y)|| 
         isCross(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y)||
         isCross(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y)|| 
         isCross(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) isNone = false;
        if (isNone) {
            cout << 0 << '\n';
            continue;
        }
 
        //2. 교점 무한 -> 좌표 기준으로만 정렬해서, y는 뭐가큰지 모르니까 두 경우 다 고려
        if (l1.x == l2.x && l1.x == xmin) {
            if ((l1.y < ymax) && (l2.y > ymin) || (l2.y < ymax) && (l1.y > ymin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        else if (l1.x == l2.x && l1.x == xmax) {
            if ((l1.y < ymax) && (l2.y > ymin) || (l2.y < ymax) && (l1.y > ymin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        else if (l1.y == l2.y && l1.y == ymax) {
            if ((l1.x < xmax) && (l2.x > xmin)|| (l2.x < xmax) && (l1.x > xmin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        else if (l1.y == l2.y && l1.y == ymin) {
            if ((l1.x < xmax) && (l2.x > xmin)|| (l2.x < xmax) && (l1.x > xmin)) {
                cout << 4 << '\n';
                continue;
            }
        }
        
        int cnt_rect_line = 0, cnt_rect_point = 0;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y)) cnt_rect_line++;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y)) cnt_rect_line++;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y)) cnt_rect_line++;
        if (isCross_rect_line(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) cnt_rect_line++;
 
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y)) cnt_rect_point++;
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y)) cnt_rect_point++;
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y)) cnt_rect_point++;
        if (isCross_rect_point(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) cnt_rect_point++;
 
        cout << cnt_rect_line + cnt_rect_point/2 << '\n';
    }
    return 0;
}