[백준] 20670 미스테리 싸인

⚡백준 20670 미스테리 싸인

• https://www.acmicpc.net/problem/20670

• 볼록 다각형 내부 점 판별 문제

• 점에서 그은 반직선과 다각형이 교차하는 횟수를 이용하는 방법
  -> 다각형의 모든 변에 대해 교차를 확인하므로 O(N)의 시간 복잡도를 갖는다
  (N: 다각형의 변의 개수)

• ccw를 이용하여 판별하는 방법
  -> 다각형이 이미 만들어져 있다는 가정하에 O(lgN)의 시간 복잡도를 갖는다

풀이

• 시간 초과가 나지 않게 주의할 점:
  -> isInside(dot q, polygon p): polygon의 값을 복사하여 매개변수로 넘겨주게 되면, polygon의 크기가 매우 크기 때문에 오버 헤드가 발생한다
  -> isInside(dot q, polygon& p): polygon의 주소를 매개변수로 넘겨주어야 한다

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> dot;
typedef vector<dot> polygon;

int ccw(dot p, dot a, dot b) {
	a.first -= p.first; a.second -= p.second;
	b.first -= p.first; b.second -= p.second;
	
	ll cross = a.first * b.second - a.second * b.first;

	if (cross > 0LL) return 1;
	else if (cross < 0LL) return -1;
	else return 0;
}

bool isInside(dot q, polygon& p){
	int n = p.size();

	//1. 점 q가 p내부에 있기 위한 첫번째 조건
	if (ccw(p[0], p[1], q) < 0) return false;
	if (ccw(p[0], p[n-1], q) > 0) return false;

	//2. 점 q가 p의 내부 중 어느 구간에 있는지 이분 탐색
	int lo = 1, hi = n - 1;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;

		if (ccw(p[0],p[mid], q) > 0) 
			lo = mid;
		else 
			hi = mid;
	}

	//3. 점 q가 p내부에 있기 위한 마지막 조건
	return ccw(p[lo], q, p[hi]) < 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, k;
	cin >> n >> m >> k;

	//다각형의 점 반시계 방향으로 주어진다
	polygon a, b;
	ll x, y;
	for (int i = 0; i < n; ++i) {
		cin >> x >> y;
		a.push_back({ x, y });
	}
	for (int i = 0; i < m; ++i) {
		cin >> x >> y;
		b.push_back({ x, y });
	}

	int wrong = 0;
	for (int i = 0; i < k; ++i) {
		cin >> x >> y;
		dot q = { x, y };

		if (!isInside(q, a) || isInside(q, b)) ++wrong;
	}

	if (wrong == 0) cout << "YES";
	else cout << wrong;

	return 0;
}