백준, boj) 2254. 감옥 건설 ( C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/2254

2254번: 감옥 건설

2. 문제 개요

소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다.

소들은 (Px, Py)의 위치에 감옥을 짓고 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려고 한다. 감옥은 하나의 점으로 표현된다. 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야하고, 담 안에 포함되는 담이 있다면 완전히 감싸야한다. 같은 일직선상에 있어서도 안됨.

이러한 담 기둥들이 주어졌을 때, 겹치지 않는 최대의 중첩된 담의 겹 수를 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

Convex hull문제.

감옥을 기준으로 둘러싸야한다.

해당 Convex hull안에 감옥이 존재하는가 판별하는 방법은 Convex hull을 이루는 모든 Vector 들에 대해서 ccw함수를 실행했을때의 값이 모두 동일해야 한다는 점이다. 

 

ex) convex hull을 (1,2,3,4,5)가 만들고, 감옥의 좌표가 0이라고할때, 1->2 벡터와 0 ccw값, 2->3과 0, 3->4, 4->5, 5->1과 0의 ccw값이 모두 같아야 한다는 것이다.

 

그리고 Convex hull을 만들었고 내부에 감옥이 있다면 그 점들은 배제하여야 한다.

 

4. 문제 풀이

convex hull 알고리즘은 O(nlogn)이기 때문에 N=1000이고 크게 부담은 없다.

그래서 가장 고민했던 점을 제외하는 부분은 Set으로 골라냈고, vector를 새로 만든다고 생각하고 그냥 다시 복사해주었다. 예를 들면 구조체에 bool 변수를 두어 convex hull로 사용된 점이다 라고 표기해도 되지만 너무 불편했다.(정렬하는 데 있어서)

여튼 이 문제의 풀이는

1. Convex hull알고리즘을 수행한다.

2. Convex hull를 이루는 점들에 대해서 감옥이 내부에 있는지 판별한다. ( 문제 힌트란에 판별법 적었음)

  True 1) 내부에 있다면, 정답에 1겹을 추가하고, Convex hull을 이루었던 점들을 배제한다.

  True 2) 1번으로 이동        

 

  False 1) 정답을 출력하고 프로그램을 종료.

위와 같다. 1번같은 경우는 다른 컨벡스 헐 문제와 겹치므로 2번 부분을 살펴보면,

컨벡스 헐 정점의 정보가 있는 스택을 1번 복사한다.

그래서 그 복사한 스택을 사용해서 감옥이 해당 컨벡스헐의 내부에 있는지 확인한다.

 

첫 번째->두 번째 벡터와 ccw검사를 하고, 쭉 하다가 중요한 부분은 마지막->첫 번째 벡터도 검사해야 한다는 점이다.!

 

그런데 이거 말고 특별한 부분은 없다. 그냥 점 제외할 때는 set을 사용해서 제외했다. 시간이 널널했기 때문에..

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
using namespace std;

struct Point {
	int x, y;
	int p, q;

	Point() {}
	Point(int x_, int y_, int p_ = 0, int q_ = 0) :x(x_), y(y_), p(p_), q(q_) {}

	bool operator < (const Point &a)
	{
		if (1LL * q*a.p != p * a.q) return 1LL * q*a.p < 1LL * p*a.q;
		if (y != a.y)	return y < a.y;
		return x < a.x;
	}
};

long long ccw(const Point &a, const Point &b, const Point &c)
{
	long long val = 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (c.x - a.x)*(b.y - a.y);
	if (val < 0)
		return -1;
	else if (val == 0)
		return 0;
	else return 1;
}

vector<Point> v;

int main()
{
	int n;
	scanf("%d", &n);

	Point cow;
	scanf("%d %d", &cow.x, &cow.y);

	for (int i = 0; i < n; ++i)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		v.push_back(Point(x, y));
	}

	bool go = true;
	int ans = 0;
	
	while (go)
	{
		sort(v.begin(), v.end());
		for (int i = 1; i < v.size(); ++i)
		{
			v[i].p = v[i].x - v[0].x;
			v[i].q = v[i].y - v[0].y;
		}

		sort(++v.begin(), v.end());

		vector<Point> temp = v;
		stack<int> s, backup;
		s.push(0);
		s.push(1);
		int next = 2;

		while (next < v.size())
		{
			while (s.size() >= 2)
			{
				int first, second;
				second = s.top();
				s.pop();
				first = s.top();
				if (ccw(v[first], v[second], v[next]) > 0)
				{
					s.push(second);
					break;
				}
			}
			s.push(next++);
		}
		//convex hull
		backup = s;
		int srt = s.top();
		int first = s.top(); s.pop();
		int second = s.top(); s.pop();

		long long chk = ccw(v[first], v[second], cow);
		bool inner = true;
		while (!s.empty())
		{
			first = second;
			second = s.top();
			s.pop();

			if (chk != ccw(v[first], v[second], cow))
			{
				inner = false;
				break;
			}
		}
		if (chk != ccw(v[second], v[srt], cow))
			inner = false;
		
		if (inner)
		{
			ans++;

			set<int> index;
			for (int i = 0; i < v.size(); ++i)
				index.insert(i);

			while (!backup.empty())
			{
				index.erase(backup.top());
				backup.pop();
			}

			v.clear();
			for (auto iter = index.begin(); iter != index.end(); ++iter)
				v.push_back(temp[(*iter)]);
		}
		else
		{
			break;
		}

		if (v.size() < 3)	break;
	}

	printf("%d", ans);
	return 0;
}

 

6. 실행 결과

댓글 지적 환영입니다~^^