BOJ 9875 - Cow Curling 링크
(2023.04.28 기준 P2)

문제

두 팀의 각 N개의 돌이 얼음판 위에 있다. 돌이 이루는 삼각형 안에 상대방 돌이 있다면 1점을 얻는다고 할 때, 각 팀의 점수 계산 후 출력.

알고리즘

볼록 껍질, 볼록 다각형 내부의 점 판정

풀이

모든 삼각형마다 상대방 돌이 있는지 일일이 확인하면 당연히 TLE가 날 것이다.
모든 삼각형이 이루는 면적은 모든 돌들의 볼록 껍질의 면적과 같다. 이는 직관적이고 자명하다.
그러므로, 각 팀마다의 볼록 껍질을 구한 후에 상대방 돌이 볼록 껍질 안에 들어가 있는지 판정하면 된다.
점 판정은 두가지 방법이 있다.
1. O(N)

볼록 껍질의 선을 한 방향으로 훑으면서 판정하고자 하는 점과의 CCW를 확인하는 방법이다.
만약 내부에 있지 않다면 CCW의 방향이 전부 일치하지 않는다.
2. O(lg N)

볼록 껍질의 0번 점과 어떤 한 점을 잇는 선분이 판정하고자 하는 점을 포함하는 최소한의 점을 찾아 CCW의 방향을 확인하는 것이다.

이 문제에서 판정법은 O(N)인 방법을 쓰면 시간 초과가 난다. 그러므로 O(lg N) 방법을 써서 AC를 받자.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

ll ccw(pll a, pll b, pll c){
    return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}

bool is_inside(vector<pll> hull, pll point){
    int sz = hull.size();

    // 볼록 껍질의 개수가 2이면 (돌들이 일직선을 이루면)
    // ccw가 0이고, 직선의 양 끝점 사이에 점이 있어야 한다.
    if (sz == 2){
        return !ccw(hull[0], hull[1], point) && min(hull[0], hull[1]) <= point && point <= max(hull[0], hull[1]);
    }

    // 점을 포함하는 최소한의 선을 찾는다.
    int st = 2, en = sz - 1, mid;
    while (st < en){
        mid = (st + en) >> 1;
        if (ccw(hull[0], hull[mid], point) < 0) en = mid;
        else st = mid + 1;
    }

    // 찾은 선과 그 직전의 선이 이루는 삼각형 안에 점이 있는지 판정
    return ccw(hull[0], hull[st - 1], point) >= 0 && ccw(hull[st - 1], hull[st], point) >= 0 && ccw(hull[st], hull[0], point) >= 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    vector<pll> A, B;
    for (int i = 0, x, y; i < N; i++) cin >> x >> y, A.push_back({x, y});
    for (int i = 0, x, y; i < N; i++) cin >> x >> y, B.push_back({x, y});
    sort(A.begin(), A.end()), sort(B.begin(), B.end());

    vector<pll> down, up, hull_A, hull_B;
    // A 팀의 볼록 껍질
    int dsz = 0, usz = 0;
    for (int i = 0; i < N; i++){
        while (dsz > 1){
            if (ccw(down[dsz - 2], down[dsz - 1], A[i]) > 0) break;
            down.pop_back(), dsz--;
        }
        down.push_back(A[i]), dsz++;
    }
    for (int i = N - 1; i >= 0; i--){
        while (usz > 1){
            if (ccw(up[usz - 2], up[usz - 1], A[i]) > 0) break;
            up.pop_back(), usz--;
        }
        up.push_back(A[i]), usz++;
    }
    for (int i = 0; i < dsz - 1; i++) hull_A.push_back(down[i]);
    for (int i = 0; i < usz - 1; i++) hull_A.push_back(up[i]);

    // B 팀의 볼록 껍질
    down.clear(), up.clear(), dsz = usz = 0;
    for (int i = 0; i < N; i++){
        while (dsz > 1){
            if (ccw(down[dsz - 2], down[dsz - 1], B[i]) > 0) break;
            down.pop_back(), dsz--;
        }
        down.push_back(B[i]), dsz++;
    }
    for (int i = N - 1; i >= 0; i--){
        while (usz > 1){
            if (ccw(up[usz - 2], up[usz - 1], B[i]) > 0) break;
            up.pop_back(), usz--;
        }
        up.push_back(B[i]), usz++;
    }
    for (int i = 0; i < dsz - 1; i++) hull_B.push_back(down[i]);
    for (int i = 0; i < usz - 1; i++) hull_B.push_back(up[i]);

    // A 팀의 볼록 껍질 안에 포함된 B 팀의 돌의 개수 구하기
    int score_A = 0;
    for (int i = 0; i < N; i++) if (is_inside(hull_A, B[i])) score_A++;

    // B 팀의 볼록 껍질 안에 포함된 A 팀의 돌의 개수 구하기
    int score_B = 0;
    for (int i = 0; i < N; i++) if (is_inside(hull_B, A[i])) score_B++;

    cout << score_A << ' ' << score_B;
}

• Python

import sys; input = sys.stdin.readline

def ccw(a, b, c):
    return (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0])

def is_inside(hull, point):
    # 볼록 껍질의 개수가 2이면 (돌들이 일직선을 이루면)
    # ccw가 0이고, 직선의 양 끝점 사이에 점이 있어야 한다.
    if len(hull) == 2:
        return not ccw(hull[0], hull[1], point) and min(hull[0], hull[1]) <= point <= max(hull[0], hull[1])

    # 점을 포함하는 최소한의 선을 찾는다.
    start = 0; end = len(hull) - 1
    while start < end:
        mid = (start + end) >> 1
        if ccw(hull[0], hull[mid], point) < 0:
            end = mid
        else:
            start = mid + 1

    # 찾은 선과 그 직전의 선이 이루는 삼각형 안에 점이 있는지 판정
    return ccw(hull[0], hull[start - 1], point) >= 0 and ccw(hull[start - 1], hull[start], point) >= 0 and ccw(hull[start], hull[0], point) >= 0

N = int(input())
A = sorted(tuple(map(int, input().split())) for _ in range(N))
B = sorted(tuple(map(int, input().split())) for _ in range(N))

# A 팀의 볼록 껍질
down = []
for i in range(N):
    while len(down) > 1:
        if ccw(down[-2], down[-1], A[i]) > 0:
            break
        down.pop()
    down.append(A[i])
up = []
for i in range(N - 1, -1, -1):
    while len(up) > 1:
        if ccw(up[-2], up[-1], A[i]) > 0:
            break
        up.pop()
    up.append(A[i])
hull_A = down[:-1] + up[:-1]

# B 팀의 볼록 껍질
down = []
for i in range(N):
    while len(down) > 1:
        if ccw(down[-2], down[-1], B[i]) > 0:
            break
        down.pop()
    down.append(B[i])
up = []
for i in range(N - 1, -1, -1):
    while len(up) > 1:
        if ccw(up[-2], up[-1], B[i]) > 0:
            break
        up.pop()
    up.append(B[i])
hull_B = down[:-1] + up[:-1]

# A 팀의 볼록 껍질 안에 포함된 B 팀의 돌의 개수 구하기
score_A = 0
for i in range(N):
    if is_inside(hull_A, B[i]):
        score_A += 1

# B 팀의 볼록 껍질 안에 포함된 A 팀의 돌의 개수 구하기
score_B = 0
for i in range(N):
    if is_inside(hull_B, A[i]):
        score_B += 1

print(score_A, score_B)