BOJ 20670 - 미스테리 싸인 링크
(2023.09.07 기준 P3)

문제

볼록 다각형 A와 A의 내부에 존재하는 볼록 다각형 B가 주어진다.
태영이의 싸인은 K개의 점을 차례로 이은 다각선이며, 모든 점은 A의 내부, B의 외부에 있어야 한다.
조건을 위배하는 점의 개수 출력

알고리즘

볼록 다각형 내부의 점 판정

풀이

결국은, K개의 점 중 몇 개의 점이 A의 외부나 B의 내부에 있는지 확인하는 문제이다.
그러므로 볼록 다각형 내부의 점 판정 알고리즘을 사용하여 K개의 모든 점을 볼록 다각형 A와 B에 대해 검사하면 된다.

그런데 N과 M이 최대 10,000이며 K는 최대 300,000이라서 O(N) 알고리즘을 사용하면 (10,000 + 10,000) × 300,000 = 6,000,000,000이므로 TLE다.
그러므로 BOJ 9875 - Cow Curling 풀이에서 설명한 O(log 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 (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool is_inside_convex(vector<pll> &hull, pll point){

    // 점을 포함하는 최소한의 선을 찾는다.
    int st = 2, en = hull.size() - 1;
    while (st < en){
        int 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, M, K; cin >> N >> M >> K;

    // 도형 A
    vector<pll> A(N); for (int i = 0; i < N; i++) cin >> A[i].x >> A[i].y;

    // 도형 B
    vector<pll> B(M); for (int i = 0; i < M; i++) cin >> B[i].x >> B[i].y;

    // 태영이의 싸인을 구성하는 점들
    vector<pll> points(K); for (int i = 0; i < K; i++) cin >> points[i].x >> points[i].y;

    int result = 0; // 조건을 위반한 점의 개수
    for (auto point: points)
        // 점이 A 안에 없거나 B 안에 있으면 조건을 위반하게 된다.
        if (!is_inside_convex(A, point) || is_inside_convex(B, point)) result++;

    if (result) cout << result;
    else cout << "YES";
}

• Python

import sys; input = sys.stdin.readline

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

	# 점을 포함하는 최소한의 선을 찾는다.
    st = 2; en = len(hull) - 1
    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 and ccw(hull[st - 1], hull[st], point) >= 0 and ccw(hull[st], hull[0], point) >= 0

N, M, K = map(int, input().split())

# 도형 A
P = list(map(int, input().split()))
A = [(P[i << 1], P[i << 1 | 1]) for i in range(N)]

# 도형 B
P = list(map(int, input().split()))
B = [(P[i << 1], P[i << 1 | 1]) for i in range(M)]

# 태영이의 싸인을 구성하는 점들
P = list(map(int, input().split()))
points = [(P[i << 1], P[i << 1 | 1]) for i in range(K)]

result = 0 # 조건을 위반한 점의 개수
for point in points:
    # 점이 A 안에 없거나 B 안에 있으면 조건을 위반하게 된다.
    if not is_inside_convex(A, point) or is_inside_convex(B, point):
        result += 1

print(result if result else "YES")