F. Intersections

2차원 좌표계에 모든 변이 x축과 평행하거나 y축에 평행한 직사각형 하나와 선분 하나가 주어졌을 때 교차점의 개수를 구하는 문제다.

이 문제를 편하게 해결하기 위해 두 선분이 주어졌을 때 생기는 교차점의 개수를 세는 함수 intersect(line a, line b)를 생각하자.

두 선분이 서로 다른 직선 성분일 경우, ccw 함수를 이용하여 두 선분이 교차하는지 확인할 수 있다. 만약 교차하면 생기는 교차점의 개수는 1개이며, 교차하지 않는다면 교차점의 개수는 0이다.

ccw(point a, point b, point c): (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y)

점 a에서 점 b로 갔다가 점 c로 갔을 때 꺽이는 방향이 시계 방향인지 반시계 방향인지 판별하는 함수

(값이 양수인 경우 반시계 방향, 값이 음수인 경우 시계 방향, 값이 0인 경우 세 점이 한 직선 위에 있음.)

두 선분이 같은 직선 성분일 경우, 교차점의 개수가 무한할 수 있다. 두 선분이 점에서 만나는 경우 교차점의 개수는 1개이며, 선에서 만나는 경우 교차점의 개수는 무한이다. 이 경우 계산을 편하게 하기 위해 선분의 양 끝 점 좌표의 x, y 성분을 더하여 1차원 좌표계로 표현할 수 있다.

intersect 함수 구현에 대한 자세한 설명은 생략한다. 함수가 구현이 되면, 직사각형을 구성하는 선분들과 주어진 선분과 교차점 개수를 구해 더한다. 이 때, 같은 교차점이 중복으로 세어질 수 있는데, 이런 경우 그 교차점은 직사각형의 꼭지점이 된다. 따라서, 직사각형 꼭지점이 선분 위에 있는 경우 세어준 값을 하나 감소시킨다.

#include <stdio.h> #include <algorithm> using namespace std; int T; struct P{ int x, y; int s(){ return this->x + this->y; } } B[4]; struct L{ L(){} L(const P &a, const P &b): a(a), b(b){} P a, b; } A; int ccw(const P &a, const P &b, const P &c) { int k = (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); if (k > 0) return 1; if (k) return -1; return 0; } int insc(L p, L q) { if (!ccw(p.a, p.b, q.a) && !ccw(p.a, p.b, q.b)){ if (p.a.s() > p.b.s()) swap(p.a, p.b); if (q.a.s() > q.b.s()) swap(q.a, q.b); int a = p.a.s(), b = p.b.s(), c = q.a.s(), d = q.b.s(); if (b < c || d < a) return 0; if (b == c || a == d) return 1; return -1; } if (ccw(p.a, p.b, q.a) == ccw(p.a, p.b, q.b) || ccw(q.a, q.b, p.a) == ccw(q.a, q.b, p.b)) return 0; return 1; } int main() { int i; for (scanf("%d", &T);T--;){ scanf("%d%d%d%d", &B[0].x, &B[0].y, &B[2].x, &B[2].y); scanf("%d%d%d%d", &A.a.x, &A.a.y, &A.b.x, &A.b.y); B[1].x = B[2].x, B[1].y = B[0].y; B[3].x = B[0].x, B[3].y = B[2].y; int ans = 0; for (i=0; i<4; i++){ int v = insc(A, L(B[i], B[(i+1)%4])); if (v == -1) break; ans += v; v = insc(A, L(B[i], B[i])); if (v) ans--; } printf("%d\n", i<4?4:ans); } }