[Algorithm] cpp 백준 3878번: 점 분리

문제

링크: https://www.acmicpc.net/problem/3878
요약: 평면상의 검은 점 집합과 흰 점 집합을 하나의 직선으로 서로 다른 반평면에 완전히 분리할 수 있는지 판별합니다. 직선은 어떤 점도 지나가면 안 되므로 접촉(점이나 변 위)에 해당해도 분리 불가입니다.

입력/출력

여러 테스트 케이스가 주어집니다. 각 케이스마다 검은 점 개수 n, 흰 점 개수 m이 주어지고, 이어서 각 점의 정수 좌표가 주어집니다.
각 케이스마다 분리가 가능하면 YES, 불가능하면 NO를 출력합니다.

접근 개요

직선으로 두 집합이 엄격히 분리되려면 두 집합의 볼록껍질이 서로 교차하거나 닿지 않아야 합니다. 즉, 두 볼록다각형이 완전히 서로 떨어져 있어야 합니다.
따라서 각 집합의 볼록껍질을 만들고, 다각형 간 교차(선분 교차, 한쪽 다각형이 다른 쪽 내부/경계 포함)를 검사해 접촉·교차가 있으면 NO, 전혀 없으면 YES입니다.

알고리즘

검은 점, 흰 점 각각에 대해 단조 체인(Monotone Chain)으로 볼록껍질을 생성합니다. 퇴화(점·선분) 케이스도 그대로 유지합니다.
두 볼록껍질에 대해 다음을 검사합니다.
- 변-변 선분 교차가 있는가? (경계 접촉 포함)
- 한 다각형의 임의 한 점이 다른 다각형 내부 또는 경계에 있는가? (점 포함 검사)
위 조건 중 하나라도 참이면 접촉/교차이므로 NO. 전부 거짓이면 YES.

올바름 근거(요지): 두 집합의 선형 분리 가능성은 그 볼록껍질의 선형 분리 가능성과 동치입니다. 또, 한 점도 직선을 지나면 안 되므로 경계 접촉 역시 허용되지 않습니다.

복잡도

볼록껍질: O((n+m) log(n+m))
다각형 교차 검사: O(h_b · h_w) (각 껍질 꼭짓점 수)
전체: O((n+m) log(n+m))

구현 (C++)

  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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Point {
	long long x, y;
	bool operator<(const Point& other) const {
		if (x != other.x) return x < other.x;
		return y < other.y;
	}
	bool operator==(const Point& other) const {
		return x == other.x && y == other.y;
	}
};

static long long cross(const Point& a, const Point& b, const Point& c) {
	// (b - a) x (c - a)
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

static bool onSegment(const Point& a, const Point& b, const Point& p) {
	if (cross(a, b, p) != 0) return false;
	return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
	       min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

static bool segmentsIntersect(const Point& a, const Point& b, const Point& c, const Point& d) {
	long long ab_c = cross(a, b, c);
	long long ab_d = cross(a, b, d);
	long long cd_a = cross(c, d, a);
	long long cd_b = cross(c, d, b);

	if (ab_c == 0 && onSegment(a, b, c)) return true;
	if (ab_d == 0 && onSegment(a, b, d)) return true;
	if (cd_a == 0 && onSegment(c, d, a)) return true;
	if (cd_b == 0 && onSegment(c, d, b)) return true;

	bool ab_strict = (ab_c > 0 && ab_d < 0) || (ab_c < 0 && ab_d > 0);
	bool cd_strict = (cd_a > 0 && cd_b < 0) || (cd_a < 0 && cd_b > 0);
	return ab_strict && cd_strict;
}

static vector<Point> convexHull(vector<Point> pts) {
	if (pts.size() <= 1) return pts;
	sort(pts.begin(), pts.end());
	pts.erase(unique(pts.begin(), pts.end()), pts.end());
	if (pts.size() <= 1) return pts;

	vector<Point> lower, upper;
	for (const auto& p : pts) {
		while (lower.size() >= 2 && cross(lower[lower.size()-2], lower.back(), p) <= 0)
			lower.pop_back();
		lower.push_back(p);
	}
	for (int i = (int)pts.size() - 1; i >= 0; --i) {
		const auto& p = pts[i];
		while (upper.size() >= 2 && cross(upper[upper.size()-2], upper.back(), p) <= 0)
			upper.pop_back();
		upper.push_back(p);
	}
	lower.pop_back();
	upper.pop_back();
	lower.insert(lower.end(), upper.begin(), upper.end());
	return lower;
}

// Returns: 0 = outside, 1 = inside, 2 = on boundary
static int containsPointConvexOrDegenerate(const vector<Point>& poly, const Point& p) {
	int n = (int)poly.size();
	if (n == 0) return 0;
	if (n == 1) return (poly[0] == p) ? 2 : 0;
	if (n == 2) return onSegment(poly[0], poly[1], p) ? 2 : 0;

	bool hasPos = false, hasNeg = false;
	for (int i = 0; i < n; ++i) {
		const Point& a = poly[i];
		const Point& b = poly[(i + 1) % n];
		long long c = cross(a, b, p);
		if (c == 0 && onSegment(a, b, p)) return 2;
		if (c > 0) hasPos = true;
		if (c < 0) hasNeg = true;
		if (hasPos && hasNeg) return 0; // Outside for convex polygon
	}
	return 1; // Inside (all cross products have the same sign)
}

static bool polygonsIntersectOrTouch(const vector<Point>& A, const vector<Point>& B) {
	int na = (int)A.size(), nb = (int)B.size();

	// Handle degenerate sizes
	if (na == 0 || nb == 0) return false;

	if (na == 1 && nb == 1) return A[0] == B[0];
	if (na == 1) return containsPointConvexOrDegenerate(B, A[0]) != 0;
	if (nb == 1) return containsPointConvexOrDegenerate(A, B[0]) != 0;

	// Edge intersections
	auto edgeIntersects = [&](const vector<Point>& P, const vector<Point>& Q) {
		int n = (int)P.size(), m = (int)Q.size();
		for (int i = 0; i < n; ++i) {
			Point a = P[i], b = P[(i + 1) % n];
			for (int j = 0; j < m; ++j) {
				Point c = Q[j], d = Q[(j + 1) % m];
				if (segmentsIntersect(a, b, c, d)) return true;
			}
		}
		return false;
	};
	if (edgeIntersects(A, B)) return true;

	// Containment (A inside B or B inside A)
	if (containsPointConvexOrDegenerate(B, A[0]) != 0) return true;
	if (containsPointConvexOrDegenerate(A, B[0]) != 0) return true;

	return false;
}

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

	int T;
	if (!(cin >> T)) return 0;
	while (T--) {
		int n, m;
		cin >> n >> m;

		vector<Point> black(n), white(m);
		for (int i = 0; i < n; ++i) cin >> black[i].x >> black[i].y;
		for (int i = 0; i < m; ++i) cin >> white[i].x >> white[i].y;

		// If either set is empty, trivially separable
		if (n == 0 || m == 0) {
			cout << "YES\n";
			continue;
		}

		vector<Point> hb = convexHull(black);
		vector<Point> hw = convexHull(white);

		bool touchOrIntersect = polygonsIntersectOrTouch(hb, hw);
		// Strict linear separability exists iff convex hulls are disjoint (no touch, no intersection)
		cout << (touchOrIntersect ? "NO" : "YES") << "\n";
	}
	return 0;
}