12801번: Relay

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


$O(n+m)$

간단히 정리하면 섬에 부딪히지 않고 최대 두번 직진하여 갈 수 있는 지점의 수를 구하는 문제.

ccw(a,b,c): 점 a,b,c 순으로 보았을 때 반시계 방향이면 양수, 직선이면 0, 시계 방향이면 음수
p[0...n-1]: 배
l[0...m-1]: 섬을 이루는 점들(반시계 방향으로 주어짐)

1. Mayday 메시지를 받을 수 있는 구역을 파악한다.
0번 지점에서 섬을 보았을 때, 섬을 이루는 보이는 점들 중 가장 왼쪽과 오른쪽 지점을 찾아야 한다.
ccw(l[i],l[(i+1)%m],p[0])<=0 인 경우, l[i],l[(i+1)%m] 선분은 p[0]에서 보인다.
이를 이용하여 보이는 선분을 이루는 점들 중 가장 왼쪽의 점을 l[u]
가장 오른쪽의 점을 l[v]라 하면
ccw(p[0],l[u],p[i])>=0 이거나
ccw(p[0],l[v],p[i])<=0 이거나
ccw(l[v],l[u],p[i])>=0 인
p[i]는 Mayday 메시지를 받을 수 있다.

2. 메시지를 받을 수 있는 구역을 파악한다.
위에서 구한 Mayday 메시지를 받을 수 있는 배들을 ai라 하자.
ccw(p[ai],l[j],l[(j+m-1)%m])<0이 될 때까지 반시계 방향으로 돌았을 때 u'=j
ccw(p[ai],l[j],l[(j+1)%m])>0가 될 때까지 시계 방향으로 돌았을 때 v'=j
ccw(p[ai],l[u'],p[j])>0 인 j가 없을 때 tu=ai
ccw(p[ai],l[v'],p[j])<0 인 j가 없을 때 tv=ai
그럼,
ccw(p[tu],l[u'],p[i])<0 이고
ccw(p[tv],l[v'],p[i])>0 이고
ccw(l[v'],l[u'],p[i])<0 인
p[i]만 메시지를 받을 수 없다.

#include<cstdio>
int n, m, u, v, a, b, tu, tv, r;
struct point {
    long long x, y;
}p[100000], l[100000];
long long ccw(point i, point j, point k) { return (i.x - k.x)*(j.y - k.y) - (j.x - k.x)*(i.y - k.y); }
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld%lld", &p[i].x, &p[i].y);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%lld%lld", &l[i].x, &l[i].y);
    for (int i = 0; i < m; i++) if (ccw(l[i], l[(i + 1) % m], p[0]) < 0) {
        u = v = i;
        break;
    }
    for (; ccw(p[0], l[v], l[(v + 1) % m]) <= 0; v = (v + 1) % m);
    for (; ccw(p[0], l[u], l[(u + m - 1) % m]) >= 0; u = (u + m - 1) % m);
    a = u;
    b = v;
    for (int i = 0; i < n; i++) if (ccw(p[0], l[a], p[i]) >= 0 || ccw(p[0], l[b], p[i]) <= 0) {
        for (; u^v&&ccw(p[i], l[u], l[(u + m - 1) % m]) >= 0; u = (u + m - 1) % m);
        for (; u^v&&ccw(p[i], l[v], l[(v + 1) % m]) <= 0; v = (v + 1) % m);
        if (ccw(p[tu], l[u], p[i]) > 0) tu = i;
        if (ccw(p[tv], l[v], p[i]) < 0) tv = i;
    }
    r = n - 1;
    for (int i = 1; i < n; i++) if (ccw(p[tu], l[u], p[i]) < 0 && ccw(p[tv], l[v], p[i]) > 0 && ccw(l[v], l[u], p[i]) < 0) r--;
    printf("%d", r);
    return 0;
}