[백준 2254] 감옥 건설

문제 링크 => 2254번: 감옥 건설 (acmicpc.net)

2254번: 감옥 건설

---

볼록 껍질을 이용한 문제이다.

 

볼록 껍질을 형성하는 과정은 Graham Scan 방식을 이용하여 접근하였다.

 

다각형을 형성할 때 가장 바깥쪽에 위치하는 점들을 이용하여 다각형을 형성하고 소의 위치가 다각형 내부에 존재하는지 파악하면 된다.

 

소의 위치가 다각형 내부에 존재하는지 파악하는 여부는 CCW(cow, pi, p(i+1)) 의 값이 모두 동일한 경우 존재하고 그렇지 않으면 존재하지 않는다. (p는 다각형의 한 점의 좌표를 의미함)

 

그리고 소의 위치가 다각형 내부에 존재하는 경우 counting 해주고 다각형을 형성한 점들을 전부 제거하여 또 다시 다각형을 만드는 과정을 반복한다.

 

즉, 점의 갯수가 3개 이상인 경우와 다각형 내부에 소가 존재하는지를 고려해주면 된다.

 

이 과정을 간단하게 정리하면 다음과 같다.

 

1. 가장 바깥쪽에 위치하는 점들로 만들어진 볼록 다각형을 형성한다.

2. 볼록 다각형 내부에 소가 존재하는지 판단한다.

3. 존재하는 경우 => Counting 하고 바깥쪽에 존재하는 점들을 제거하고 1번으로 이동

   존재하지 않는 경우 => Counting 한 결과를 출력한다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

class Point {
public:
	ll x, y;
	Point(ll x, ll y) {
		this->x = x;
		this->y = y;
	}
	Point operator-(Point p) {
		return Point(x - p.x, y - p.y);
	}
};

int N;
vector<Point> cow, v;
map<pair<int,int>, int> m;

void input() {

	ll x, y;
	cin >> N >> x >> y;
	cow.push_back({ x,y });
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		v.push_back({ x,y });
	}

}

ll cross(Point p1, Point p2) {
	ll ret = p1.x * p2.y - p1.y * p2.x;
	if (ret > 0) return 1;
	else if (ret == 0) return 0;
	else return -1;
}

ll cross(Point p1, Point p2, Point p3) {
	return cross(p2 - p1, p3 - p1);
}

vector<Point> graham_scan(vector<Point> a, ll &x, ll &y) {
	
	if (a.size() <= 2) return a;
	
	int N = a.size();
	swap(a[0], *min_element(a.begin(), a.end(), [](Point a, Point b) {
		if (a.y == b.y) return a.x < b.x;
		return a.y < b.y;
	}));

	x = a[0].x, y = a[0].y;

	for (int i = 1; i < N; i++) a[i] = a[i] - a[0];

	a[0].x = a[0].y = 0;
	sort(a.begin() + 1, a.end(), [](Point a, Point b) {
		ll c = cross(a, b);
		if (c == 0) return (a.x * a.x + a.y * a.y) < (b.x * b.x + b.y * b.y);
		return c > 0;
	});

	vector<Point> ret;
	for (int i = 0; i < N; i++) {
		while (ret.size() >= 2 && cross(ret[ret.size() - 2], ret[ret.size() - 1], a[i]) <= 0) ret.pop_back();
		ret.push_back(a[i]);
	}

	return ret;
}

void solve() {
	
	int cnt = 0;
	while (v.size() >= 3) {
		ll x, y, op, t = 0;
		vector<Point> res = graham_scan(v, x, y);
		Point p1 = cow[0];
		p1.x -= x, p1.y -= y;

		op = cross(p1, res[0], res[1]);
		m[{res[0].x + x, res[0].y + y}] = 1;
		m[{res[1].x + x, res[1].y + y}] = 1;

		for (int i = 1; i < res.size() - 1; i++) {
			Point p2 = res[i], p3 = res[i + 1];
			m[{res[i].x + x, res[i].y + y}] = 1;
			m[{res[i + 1].x + x, res[i + 1].y + y}] = 1;
			if (op != cross(p1, p2, p3)) {
				cout << cnt << endl;
				return;
			}
		}
		
		for (int i = 0; i < v.size(); i++) {
			if (m[{v[i].x, v[i].y}]) {
				v.erase(v.begin() + i);
				i--;
			}
		}
		cnt++;
	}
	cout << cnt << endl;
}

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

	input();
	solve();

	return 0;
}