백준 20670 (C++) 미스테리 싸인

최초 업로드: 2025-08-16 19:20:45

최근 수정 시간: 2025-08-16 19:21:09

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] 미스테리 싸인

[문제 링크](https://www.acmicpc.net/problem/20670)

## 문제 설명

취준생 태영이는 오랜 구직활동 끝에 취직에 성공했다. 여러가지 이유로 취업시장이 위축된 요즘, 가뭄의 단비 같은 일자리에 태영이는 기뻐했다. 하지만 모든 것은 계약되기 전에는 불확실한 법, 태영이는 하루빨리 근로계약서를 작성하고 싶은 마음에 밤잠을 설쳤다.

사회적 거리두기로 인한 언택트 시대, 태영이는 비대면 전자계약 서비스 모두싸인(MODUSIGN)을 이용해 근로계약서를 작성하게 되었다. 메일을 받은 후 태영이의 불안감은 사라졌고, 난생처음 작성해보는 계약서에 어떻게 하면 멋진 싸인을 할 수 있을지 행복한 고민을 시작했다.

태영이는 너무 튀지 않으면서도 독특한 느낌적인 느낌의 싸인을 만들고 싶다. 평소 기하학적인 감각이 돋보이던 태영이는 자신만의 룰을 지키며 싸인을 만드려고 한다. 태영이가 정한 룰은 다음과 같다.

<ul>
	<li>태영이는 두 개의 볼록 다각형 A와 B를 정한다.</li>
	<li>다각형 B는 완전히 A의 내부에 존재한다.</li>
	<li>태영이의 싸인은 여러 개의 점을 차례로 이은 다각선이다.</li>
	<li>태영이의 싸인을 구성하는 점은 A의 내부에 있어야 한다. 그리고 B의 외부에 있어야 한다.</li>
	<li>도형의 외곽선 상에는 싸인의 점이 존재하지 않는다.</li>
	<li>문제에서 주어지는 모든 좌표는 정수다.</li>
</ul>

<그림 1> 왼쪽부터 차례로 성공적인 싸인, B내부에 점이 존재해 실패한 싸인, A외부에 점이 존재해 실패한 싸인

두 도형 A, B의 정보와 태영이가 싸인한 다각선의 정보가 입력으로 주어질 때, 해당 싸인은 주어진 규칙을 만족하는지 판단하는 프로그램을 작성해주자. 만약 태영이의 싸인이 규칙을 위반했다면, 몇 개의 점이 규칙을 위반했는지 계산하시오.

## 입력

첫 번째 줄에는 세 개의 자연수 N, M, K 가 공백으로 구분되어 주어진다.

두 번째 줄에는 도형 A를 구성하는 N 개 점의 좌표가 공백으로 구분된 2N개의 정수로 주어진다. 각 점의 좌표는 <code>X Y</code> 형식으로 공백으로 구분되어 주어진다. 각 점은 반시계 방향 순서로 주어진다.

세 번째 줄에는 도형 B를 구성하는 M 개 점의 좌표가 공백으로 구분된 2M개의 정수로 주어진다. 각 점의 좌표는 <code>X Y</code> 형식으로 공백으로 구분되어 주어진다. 각 점은 반시계 방향 순서로 주어진다.

네 번째 줄에는 싸인을 구성하는 K개 점의 좌표가 공백으로 구분된 2K개의 정수로 주어진다. 각 점의 좌표는 <code>X Y</code> 형식으로 공백으로 구분되어 주어진다. 각 점을 차례로 이으면 태영이의 싸인이 완성된다.

<ul>
	<li>모든 좌표는 정수 값을 가진다. (-1,000,000,000 ≤ X, Y ≤ 1,000,000,000)</li>
	<li>문제에서 주어지는 점이 중복되는 경우는 존재하지 않는다.</li>
	<li>싸인의 점은 도형 A, B의 외곽선상에 존재하지 않는다.</li>
</ul>

## 출력

주어진 싸인이 태영이의 규칙을 만족한다면 "<code>YES</code>" 를 출력하시오.

만약 태영이의 규칙을 만족하지 않는다면, 조건을 위반한 점의 개수를 정수로 출력하시오.

## 풀이
#### 이분 탐색을 이용하여 볼록 다각형 내에서 점 판정을 O(KlogN)에 해결하였다.

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

typedef long long ll;

struct point {
    ll x, y;
};

ll ccw(point a, point b, point c) {
    point vec1 = {b.x-a.x, b.y-a.y};
    point vec2 = {c.x-a.x, c.y-a.y};
    return vec1.x*vec2.y - vec1.y*vec2.x;
}

bool isInside(vector<point> &hull, point p) {
 if(ccw(hull[0], hull[1], p)<0) return false;
 if(ccw(hull[0], hull[hull.size()-1], p)>0) return false;

int left=1, right=hull.size()-1;
 while(left+1<right) {
 int mid = (left+right)/2;
 if(ccw(hull[0], hull[mid], p)>0) left=mid;
 else right=mid;
 }
 return ccw(hull[left], p, hull[right])<0;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m, k; cin >> n >> m >> k;
 vector<point> A(n), B(m);
 for(int i=0;i<n;i++) cin >> A[i].x >> A[i].y;
 for(int i=0;i<m;i++) cin >> B[i].x >> B[i].y;

int cnt=0;
 while(k--) {
 point p; cin >> p.x >> p.y;
 if(!isInside(A, p) || isInside(B, p)) cnt++;
 }
 if(!cnt) cout << "YES";
 else cout << cnt;
}
```