백준 17403 가장 높고 넓은 성

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

볼록 껍질(Convex Hull) 관련 문제입니다. 주어진 점들로 층을 쌓는데

  1. 가장 층수가 높게
  2. 각 층의 넓이의 합이 가장 크게
  3. 점을 가장 작게 사용하게

의 우선순위로 성을 쌓아야 합니다.

먼저 층수를 가장 높게 성을 쌓아야 합니다. 외부에 점이 존재하는 것 보다 존재하지 않는 것이 더 이득입니다. 왜냐하면 다음 층을 쌓을 때 외부에 점이 있다면 사용하지 못하기 때문에 안쪽 점이 남도록 다각형을 만드는 것이 더 좋기 떄문입니다. 따라서 점들을 외곽에서 선택하는 것이 좋습니다.

또한 오목한 부분이 있는 것보다 볼록한 것이 더 좋습니다. 마찬가지로 오목한 부분이 있다면 오목한 점을 제외하여 볼록하게 만들 수 있고, 내부의 점을 더 남길 수 있기 때문입니다. 따라서 각 층은 볼록 껍질이라는 것을 알 수 있습니다.

넓이의 합이 가장 커야 하는 것은 볼록 껍질로 층을 쌓았을 때 충족됩니다. 그 이유는 넓이가 큰 조건이 층수를 높게 쌓아야 하는 조건과 동일하기 때문입니다.

점을 가장 작게 사용하는 것도 충족됩니다. 1과 2에 최선인 층의 형태는 볼록 껍질이기 때문에, 일직선 상에 존재하는 점을 제외시켜주는 것만 조심하면 됩니다.

따라서 볼록 껍질을 만들고 해당 볼록 껍질 내부에서 다시 볼록 껍질을 만드는 과정을 반복하면 주어진 세 가지 조건에 부합하게 층을 쌓을 수 있습니다.

볼록 껍질은 ConvexHull 스트럭트로 구현했습니다. 스트럭트 내부의 makeHull() 함수에서는 볼록 껍질을 만든 뒤 볼록 껍질에 해당하는 점들을 몇 층인지 저장해주었고 reset() 함수에서는 볼록 껍질에 사용된 점을 제외시키고 리셋시켜 주었습니다. makeHull() 함수에서 볼록 껍질을 만든 뒤 볼록 껍질을 구성하는 점들의 개수가 2개 이하라면 해당 점들은 한 층을 만들 수 없으므로 바로 return시켜 주었습니다.

#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF=(int)1e9;
const int MAXV=1001;
struct Point
{
	int idx;
	ll x,y,dx,dy;
	Point():idx(0),x(0),y(0),dx(0),dy(0) {}
	void init(Point p)
	{
		dx=x-p.x;
		dy=y-p.y;
	}
	bool operator < (const Point &p) const
	{
		if(dy*p.dx!=dx*p.dy) return dy*p.dx<dx*p.dy;
		return y==p.y?x<p.x:y<p.y;
	}
};
struct ConvexHull
{
	int siz,len;
	int ind[MAXV],lev[MAXV];
	Point pos[MAXV];
	void init()
	{
		cin>>siz;
		for(int i=0;i<siz;i++)
		{
			cin>>pos[i].x>>pos[i].y;
			pos[i].idx=i;
		}
		fill(ind,ind+MAXV,0);
		fill(lev,lev+MAXV,0);
	}
	int ccw(Point p1,Point p2,Point p3)
	{
		ll c=(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
		return c?(c>0?1:-1):0;
	}
	void makeHull(int num)
	{
		for(int i=0;i<siz;i++)
		{
			pos[i].dx=0,pos[i].dy=0;
			if(pos[i]<pos[0]) swap(pos[0],pos[i]);
		}
		for(int i=0;i<siz;i++)
		{
			pos[i].init(pos[0]);
		}
		sort(pos+1,pos+siz);
		stack<int> S;
		S.push(0); S.push(1);
		int p=2;
		while(p<siz)
		{
			while(S.size()>=2)
			{
				int p2=S.top(); S.pop();
				int p1=S.top();
				if(ccw(pos[p1],pos[p2],pos[p])>0)
				{
					S.push(p2);
					break;
				}
			}
			S.push(p++);
		}
		len=S.size();
		if(len<=2) return;
		for(int i=len-1;i>=0;i--)
		{
			ind[S.top()]=1;
			lev[pos[S.top()].idx]=num;
			S.pop();
		}
	}
	void reset()
	{
		int idx=0;
		for(int i=0;i<siz;i++)
		{
			if(ind[i]) continue;
			pos[idx++]=pos[i];
		}
		fill(ind,ind+MAXV,0);
		siz=siz-len;
		len=0;
	}
};
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ConvexHull cv;
	cv.init();
	int num=1,n=cv.siz;
	while(cv.siz>2)
	{
		cv.makeHull(num++);
		cv.reset();
	}
	for(int i=0;i<n;i++) cout<<cv.lev[i]<<" ";
	return 0;
}