Codeforces Round 113 (Div. 2) - Polygons 링크
(2023.07.26 기준 Difficulty *2100)

문제

볼록 다각형 A와 단순 다각형 B가 주어진다. B가 완전히 A에 포함되는지 판별

알고리즘

볼록 껍질

풀이

A가 B를 완전히 포함하려면, A와 B의 점을 모두 합쳐 볼록 껍질을 구해도 A 그대로가 나와야 한다.

이를 그대로 구현하면 된다.

문제 지문을 보면 'A의 선분 위에 B의 점이 있어도 안된다'. 즉, '일직선을 이뤄도 안된다'라는 조건이 있기 때문에, 볼록 껍질을 구할 때, 일직선인 경우(ccw=0)에도 포함하여 B의 점이 있는지 확인하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point{
    ll x, y;
    bool p;

    bool operator < (const Point &that) const{
        if (this->x == that.x)
            return this->y < that.y;
        return this->x < that.x;
    }
};

// 경계에도 포함되는지 확인하기 위해 세 점이 일직선을 이루어도 True 반환
bool ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y) >= 0;
}

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

    // 도형 A와 도형 B의 점들을 전부 합쳐서 저장
    vector<Point> points;

    int n; cin >> n;
    for (int i = 0, x, y; i < n; i++){
        cin >> x >> y;
        points.push_back({x, y, true}); // 도형 A는 true
    }

    int m; cin >> m;
    for (int i = 0, x, y; i < m; i++){
        cin >> x >> y;
        points.push_back({x, y, false}); // 도형 A는 false
    }

    // 볼록 껍질을 구하기 위해 정렬
    n += m;
    sort(points.begin(), points.end());

    // 볼록 껍질의 아래
    vector<Point> hull;
    int SZ = 0;
    for (int i = 0; i < n; i++){
        while (SZ > 1){
            if (ccw(hull[SZ - 2], hull[SZ - 1], points[i])) break;
            hull.pop_back(); SZ--;
        }
        hull.push_back(points[i]); SZ++;
    }

    // 볼록 껍질의 위
    int sz = SZ;
    for (int i = n - 1; i >= 0; i--){
        while (SZ > sz){
            if (ccw(hull[SZ - 2], hull[SZ - 1], points[i])) break;
            hull.pop_back(); SZ--;
        }
        hull.push_back(points[i]); SZ++;
    }

    for (int i = 1; i < SZ; i++) if (!hull[i].p){
        cout << "NO";
        return 0;
    }
    cout << "YES";
}

• Python

import sys; input = sys.stdin.readline

# 경계에도 포함되는지 확인하기 위해 세 점이 일직선을 이루어도 True 반환
def ccw(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]) >= 0

# 도형 A와 도형 B의 점들을 전부 합쳐서 저장
points = []

n = int(input())
for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y, True)) # 도형 A는 True

m = int(input())
for _ in range(m):
    x, y = map(int, input().split())
    points.append((x, y, False)) # 도형 B는 False

# 볼록 껍질을 구하기 위해 정렬
n += m
points.sort()

# 볼록 껍질의 아래
hull = []
for i in range(n):
    while len(hull) > 1:
        if ccw(hull[-2], hull[-1], points[i]):
            break
        hull.pop()
    hull.append(points[i])

# 볼록 껍질의 위
sz = len(hull)
for i in range(n - 1, -1, -1):
    while len(hull) > sz:
        if ccw(hull[-2], hull[-1], points[i]):
            break
        hull.pop()
    hull.append(points[i])

# 볼록 껍질을 이루는 점 중에서 도형 B에 포함되는 점이 있다면 NO 출력
for x, y, p in hull:
    if not p:
        print('NO')
        break
else:
    print('YES')