4544 - 'Roid Rage

문제 번역

$M$개의 다각형이 있습니다. 각 다각형끼리 교차하는지 아닌지 판단하세요. 두 개의 다각형이 내부 영역을 공유하거나(즉, 겹치는 경우) 경계점을 공유하는 경우(즉, 한 점이나 가장자리를 따라 닿는 경우)를 말합니다.

step 1

다각형의 수와 꼭짓점의 수가 적기 때문에 모든 경우를 보는 방법으로도 충분히 풀 수 있어 보입니다. 두 다각형이 있을 때, 어떤 변이 교차하면 반드시 겹친다고 할 수 있습니다. 이는 CCW를 이용해서 해결할 수 있습니다.

두 직선 $\overline{XY}$랑 $\overline{ZW}$가 있다고 해봅시다. CCW($XYZ$) * CCW($XYW$)가 음수고 CCW($ZWX$) * CCW($ZWY$)가 음수면 이는 확실히 교차한다고 할 수 있습니다.

 

만약 CCW($XYZ$) * CCW($XYW$)가 양수면 $\overline{XY}$의 한쪽 면에 $Z, W$가 있다는 뜻이므로 절대 교차하지 않습니다. CCW($ZWX$) * CCW($ZWY$)가 양수일 때도 마찬가지입니다.

만약 CCW($XYZ$) * CCW($XYW$)가 0이면 $XY$ 직선 위에 $Z$나 $W$가 있다는 뜻입니다. 이 상태에서 CCW($ZWX$) * CCW($ZWY$)가 음수라면 이 두 직선은 반드시 교차합니다.

 

양수가 있는 경우, 모두 음수인 경우, 음수가 하나인 경우를 모두 처리했습니다. 이제 두 값 모두 0인 경우가 남았습니다. 이 경우는 네 점 모두 일직선 위에 있다는 의미입니다. $X$축이나 $Y$축 기준으로 정렬한 다음 겹치는지 아닌지 판단합니다.

 

이렇게 하면 직선이 교차하는 모든 경우를 처리할 수 있습니다.

step 2

이제 하나가 다른 하나를 포함하는 경우입니다. 한 다각형의 꼭짓점에서 시작하는 아무 반직선을 그립니다. 이 반직선과 다른 다각형과 교차하는 선의 개수가 홀수개면 서로 포함 관계라는 뜻입니다.

 

이때, 반직선이 꼭짓점을 지나거나 변과 평행한 경우 처리하기가 까다롭습니다. 그러니 절대 그런 경우가 없도록 직선을 그어줍니다. 저는 반직선의 시작 좌표가 (x,y)라면 (x,y)에서 (x+1,5001)로 향하는 직선을 그어 줬습니다.

그리고 교차 판정은 CCW로 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct data {
    long long int n;
    pair<long long int, long long int> p[50];
}b[20];
long long int ccw(pair<long long int,long long int> x, pair<long long int, long long int> y, pair<long long int, long long int> z) {
    long long int x1 = x.first, y1 = x.second;
    long long int x2 = y.first, y2 = y.second;
    long long int x3 = z.first, y3 = z.second;
    long long int v = x1 * y2 + x2 * y3 + x3 * y1 - (y1 * x2 + y2 * x3 + y3 * x1);
    if (v > 0) return 1;
    if (v < 0) return -1;
    return 0;
}
long long int check(pair<long long int, long long int> x, pair<long long int, long long int> y, pair<long long int, long long int> z, pair<long long int, long long int> w) {
    pair<long long int, long long int> p[4];
    long long int i;
    for (i = 0;i < 4;i++) {
        if (x.first == y.first) p[i].first = x.second; else p[i].first = x.first;
        p[i].second = i;
    }
    sort(p, p + 4);
    if (p[0].second <= 2 && p[1].second <= 2 || p[2].second <= 2 && p[3].second <= 2) return 0;
    return 1;
}
int main() {
    long long int n, i,t,j,k,l,ttt=0,cnt;
    scanf("%lld", &t);
    while (t--) {
        cnt = 0;
        ttt++;
        scanf("%lld", &n);
        for (i = 1;i <= n;i++) {
            scanf("%lld", &b[i].n);
            for (j = 1;j <= b[i].n;j++) {
                scanf("%lld,%lld", &b[i].p[j].first, &b[i].p[j].second);
            }
            b[i].p[b[i].n + 1] = b[i].p[1];
        }
        printf("Data Set #%lld\n", ttt);
        for (i = 1;i <= n;i++) {
            for (j = i+1;j <= n;j++) {
                long long int e = 0;
                for (k = 1;k <= b[i].n;k++) {
                    for (l = 1;l <= b[j].n;l++) {
                        if (b[i].p[k] == b[j].p[l] || b[i].p[k] == b[j].p[l + 1] || b[i].p[k + 1] == b[j].p[l] || b[i].p[k + 1] == b[j].p[l + 1]) {
                            e = 1;
                            printf("%lld %lld\n", i, j);
                            break;
                        }
                        long long int v1 = ccw(b[i].p[k], b[i].p[k + 1], b[j].p[l]) * ccw(b[i].p[k], b[i].p[k + 1], b[j].p[l + 1]);
                        long long int v2 = ccw(b[j].p[l], b[j].p[l + 1], b[i].p[k]) * ccw(b[j].p[l], b[j].p[l + 1], b[i].p[k + 1]);
                        if (v1 == -1 && v2 == -1) {
                            e = 1;
                            printf("%lld %lld\n", i, j);
                            break;
                        }
                        if (v1 == 1 || v2 == 1) continue;
                        if (v1 != 0 || v2 != 0) {
                            e = 1;
                            printf("%lld %lld\n", i, j);
                            break;
                        }
                        if(check(b[i].p[k], b[i].p[k + 1], b[j].p[l], b[j].p[l + 1]) == 1) {
                            e = 1;
                            printf("%lld %lld\n", i, j);
                            break;
                        }
                    }
                    if (e == 1) break;
                }
                if (e == 1) cnt = 1;
                if (e == 1) continue;
                long long int countt = 0;
                for (k = 1;k <= b[j].n;k++) {
                    long long int v1 = ccw(b[i].p[1], { b[i].p[1].first + 1, 5001 }, b[j].p[k]) * ccw(b[i].p[1], { b[i].p[1].first + 1, 5001 }, b[j].p[k + 1]);
                    long long int v2 = ccw(b[j].p[k], b[j].p[k + 1], b[i].p[1]) * ccw(b[j].p[k], b[j].p[k + 1], { b[i].p[1].first + 1, 5001 });
                    if (v1 == -1 && v2 == -1) countt++;
                }
                if (countt % 2 == 1) {
                    cnt = 1;
                    printf("%lld %lld\n", i, j);
                    continue;
                }
                countt = 0;
                for (k = 1;k <= b[i].n;k++) {
                    long long int v1 = ccw(b[i].p[k], b[i].p[k + 1], b[j].p[1]) * ccw(b[i].p[k], b[i].p[k + 1], { b[j].p[1].first + 1, 5001 });
                    long long int v2 = ccw(b[j].p[1], { b[j].p[1].first + 1, 5001 }, b[i].p[k]) * ccw(b[j].p[1], { b[j].p[1].first + 1, 5001 }, b[i].p[k + 1]);
                    if (v1 == -1 && v2 == -1) countt++;
                }
                if (countt % 2 == 1) {
                    cnt = 1;
                    printf("%lld %lld\n", i, j);
                    continue;
                }
            }
        }
        if (cnt == 0) printf("no collisions\n");
    }
    return 0;
}