백준3878 점 분리

작성일 | In

문제 링크

  • http://icpc.me/3878

문제 출처

  • 2009 Tokyo Regional D번

사용 알고리즘

  • Convex Hull

시간복잡도

  • O(N2)

풀이

두 개의 점 그룹을 분리하는 선이 존재하는지 물어보는 문제입니다.

분리축 이론이라는 것이 있습니다.
두 볼록 다각형이 교차하지 않는다면 최소한 하나의 분리축이 존재합니다.
결국, 두 그룹의 convex hull을 각각 구해준 뒤, 두 개의 볼록껍질이 만나는지 확인해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

vector<p> a, b;
vector<p> aHull, bHull;

int ccw(p a, p b, p c){
	ll res = a.x*b.y + b.x*c.y + c.x*a.y;
	res -= b.x*a.y + c.x*b.y + a.x*c.y;
	if (res > 0) return 1;
	if (res)return -1;
	return 0;
}

ll dist(p a, p b){
	ll dx = a.x - b.x;
	ll dy = a.y - b.y;
	return dx*dx + dy*dy;
}

void init(){
	a.clear();
	b.clear();
	aHull.clear();
	bHull.clear();
}

void getHull(vector<p> &v, vector<p> &hull){
	for(auto &i : v) cin >> i.x >> i.y;
	swap(v[0], *min_element(v.begin(), v.end()));
	sort(v.begin() + 1, v.end(), [&](p &a, p &b){
		int cw = ccw(v[0], a, b);
		if (cw) return cw > 0;
		return dist(v[0], a) < dist(v[1], b);
	});
	for (auto i : v){
		while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), i) <= 0) hull.pop_back();
		hull.push_back(i);
	}
}

bool chk(p now, const vector<p> &v){
	int cnt = 0;
	pair<double, double> ii, jj;
	pair<double, double> q = {now.x, now.y};
	for(int i=0; i<v.size(); i++){
		int j = (i + 1) % v.size();
		ii = v[i], jj = v[j];
		if((ii.y > q.y) != (jj.y > q.y)){
			double X = (jj.x - ii.x) * (q.y - ii.y) / (jj.y - ii.y) + ii.x;
			if(q.x < X) cnt++;
		}
	}
	return cnt % 2 > 0;
}

bool disjoint(ll a, ll b, ll c, ll d){
	if(a > b) swap(a, b);
	if(c > d) swap(c, d);
	return b < c || d < a;
}

bool crash(p a, p b, p c, p d){
	int ab = ccw(a, b, c) * ccw(a, b, d);
	int cd = ccw(c, d, a) * ccw(c, d, b);
	if(ab == 0 && cd == 0){
		return !disjoint(a.x, b.x, c.x, d.x) && !disjoint(a.y, b.y, c.y, d.y);
	}
	return ab <= 0 && cd <= 0;
}

void solve(){
	init();
	int n, m; cin >> n >> m;
	a.resize(n); b.resize(m);
	getHull(a, aHull); getHull(b, bHull);

	int ans = 0;

	if(chk(aHull[0], bHull) || chk(bHull[0], aHull)) ans = 1;

	for(auto i : aHull) if(chk(i, bHull)) ans = 1;
	for(auto i : bHull) if(chk(i, aHull)) ans = 1;

	n = aHull.size();
	m = bHull.size();
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(crash(aHull[i], aHull[(i+1)%n], bHull[j], bHull[(j+1)%m])) ans = 1;
		}
	}
	if(ans) cout << "NO\n";
	else cout << "YES\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) solve();
}