[BOJ] 3878 점 분리

문제: https://www.acmicpc.net/problem/3878

 

소스 코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <string.h>
using namespace std;

typedef long double ll;
typedef pair<ll, ll> P;
int startpoint, tc, n, m;
ll ax, ay;
vector<P> black, white;
vector<int> v1,v2;

bool cmp(const P a, const P b) {
	if ((ax - b.first) * (ay - a.second) == (ax - a.first) * (ay - b.second)) {
		if (a.second == b.second)
			return a.first < b.first;
		else
			return a.second < b.second;
	}
	else {
		return (ax - b.first) * (ay - a.second) < (ax - a.first) * (ay - b.second);
	}
}


ll ccw(P p1, P p2, P p3) {
	return p1.first * p2.second + p2.first * p3.second + p3.first * p1.second - (p1.first * p3.second + p3.first * p2.second + p2.first * p1.second);
}

// 두 선분이 만나는지 판단
bool cross(P p1, P p2, P p3, P p4) {
	ll ccw1 = ccw(p1, p2, p3);
	ll ccw2 = ccw(p1, p2, p4);
	ll ccw3 = ccw(p3, p4, p1);
	ll ccw4 = ccw(p3, p4, p2);

	if (ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0) {
		if (min(p1.first, p2.first) > max(p3.first, p3.first) ||
			min(p1.second, p2.second) > max(p3.second, p4.second) ||
			min(p3.first, p3.first) > max(p1.first, p2.first) ||
			min(p3.second, p4.second) > max(p1.second, p2.second)) return false;
	}
	if (ccw1 * ccw2 <= 0 && ccw3 * ccw4 <= 0) return true;
	return false;
}

bool meet(P p1, P p2, P p3) {
	if (ccw(p1, p2, p3) == 0) {
		// 한 선분과 한 점이 일직선에 존재할 때, 겹치는 지 판단
		if (max(p1.first, p2.first) < p3.first
			|| max(p1.second, p2.second) < p3.second
			|| min(p1.first, p2.first) > p3.first
			|| min(p1.second, p2.second) > p3.second) return false;
		else true;
	}
	else return false;
}

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

	cin >> tc;
	while (tc--) {
		cin >> n >> m;

		v1.clear();
		v2.clear();
		black.clear();
		white.clear();
		startpoint = 0;
		for (int i = 0; i < n; i++) {
			ll q, w;
			cin >> q >> w;
			black.push_back({ q,w });
			if (w < black[startpoint].second) startpoint = i;
			else if (w == black[startpoint].second && q < black[startpoint].first) startpoint = i;
		}

		ax = black[startpoint].first;
		ay = black[startpoint].second;

		sort(black.begin(), black.end(), cmp);

		startpoint = 0;
		for (int i = 0; i < m; i++) {
			ll q, w;
			cin >> q >> w;
			white.push_back({ q,w });
			if (w < white[startpoint].second) startpoint = i;
			else if (w == white[startpoint].second && q < white[startpoint].first) startpoint = i;
		}

		bool res = true;
		// black으로 볼록껍질 만들기

		int idx = 2;
		int vp = 1;
		if(black.size()>0) v1.push_back(0);
		if(black.size()>1) v1.push_back(1);

		while (black.size()>2) {
			if (idx == n || vp < 1) break;
			ll ccwV = ccw(black[v1[vp - 1]], black[v1[vp]], black[idx]);
			if (ccwV >= 0) {
				v1.push_back(idx);
				idx++;
				vp++;
			}
			else if (ccwV < 0) {
				v1.pop_back();
				vp--;
			}
			else {
				v1.pop_back();
				v1.push_back(idx);
				idx++;
			}
		}
		if (v1.size() > 2) {
			for (int i = 0; i < m; i++) {
				int chk = 0;
				ll tmp = ccw(black[v1[vp]], black[v1[0]], white[i]);
				if (tmp > 0) chk = 1;
				else if (tmp < 0) chk = -1;
				else if(meet(black[v1[vp]], black[v1[0]], white[i])){
					res = false;
					break;
				}
				bool inside = true;
				for (int j = 0; j < vp; j++) {
					tmp = ccw(black[v1[j]], black[v1[j + 1]], white[i]);
					int chk2 = 0;
					if (tmp > 0) chk2 = 1;
					else if (tmp < 0) chk2 = -1;
					else if(meet(black[v1[j]], black[v1[j + 1]], white[i])) {
						res = false;
						break;
					}
					if (chk != chk2) {
						inside = false;
						break;
					}
				}
				if (inside) {
					res = false;
					break;
				}
			}
		}
		
		
		if (res) {
			//white로 볼록껍질 만들기
			ax = white[startpoint].first;
			ay = white[startpoint].second;

			sort(white.begin(), white.end(), cmp);
			idx = 2;
			vp = 1;
			v2.push_back(0);
			if (white.size()>1) v2.push_back(1);

			while (white.size()>2) {
				if (idx == m || vp < 1) break;
				ll ccwV = ccw(white[v2[vp - 1]], white[v2[vp]], white[idx]);
				if (ccwV >= 0) {
					v2.push_back(idx);
					idx++;
					vp++;
				}
				else if (ccwV < 0) {
					v2.pop_back();
					vp--;
				}
			}
			if (v2.size() >2) {
				for (int i = 0; i < n; i++) {
					int chk = 0;
					ll tmp = ccw(white[v2[vp]], white[v2[0]], black[i]);
					if (tmp > 0) chk = 1;
					else if (tmp < 0) chk = -1;
					else if(meet(white[v2[vp]], white[v2[0]], black[i])){
						res = false;
						break;
					}
					bool inside = true;
					for (int j = 0; j < vp; j++) {
						tmp = ccw(white[v2[j]], white[v2[j + 1]], black[i]);
						int chk2 = 0;
						if (tmp > 0) chk2 = 1;
						else if (tmp < 0) chk2 = -1;
						else if (meet(white[v2[j]], white[v2[j + 1]], black[i])) {
							res = false;
							break;
						}
						if (chk != chk2||chk2==0) {
							inside = false;
							break;
						}
					}
					if (inside) {
						res = false;
						break;
					}
				}
			}
			
		}
		if (res) {
			int len1 = v1.size(), len2=v2.size();
			if (len1 == 2 && len2== 1) {
				if (meet(black[v1[0]], black[v1[1]], white[0])) res = false;
			}
			else if( len1== 1 && len2 == 2) {
				if (meet(white[v2[0]], white[v2[1]], black[0])) res = false;
			}
			else if (len1 >= 2 && len2 >= 2) {
				for (int i = 0; i < len1; i++) {
					for (int j = 0; j < len2; j++) {
						P p1, p2, p3, p4;
						if (i == len1 - 1) {
							p1 = black[v1[len1-1]];
							p2 = black[v1[0]];
						}
						else {
							p1 = black[v1[i]];
							p2 = black[v1[i + 1]];
						}
						if (j == len2 - 1) {
							p3 = white[v2[len2 - 1]];
							p4 = white[v2[0]];
						}
						else {
							p3 = white[v2[j]];
							p4 = white[v2[j + 1]];
						}
						if (cross(p1,p2,p3,p4)) {
							res = false;
							break;
						}
					}
					if (!res) break;
				}
			}
		}
		if (res) cout << "YES\n";
		else cout << "NO\n";
	}
	
	return 0;
}