백준 3679번 - 단순 다각형

 

 

 

* 문제 링크

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

3679번: 단순 다각형

 

 

 

 

문제 내용 요약

 

 

주어진 점 N ( 3 ≤ N ≤ 2000 ) 개로 아무렇게나 다각형을 만들자

 

다각형의 선분은 무조건 점에서만 교차해야하고, 모든 점이 한 직선에 있는 경우는 없다.

 

 

 

 

접근법

 

 

계속해서 컨벡스 헐 문제를 풀어왔다면, 접근하기에 어렵지는 않을 것이다.

 

사실 컨벡스 헐까지 가지 않고, 각도에 따라 정렬할 줄만 알면 된다.

 

아래는 관련 배경 지식 링크다. 둘 중에 후자는 사실 안 봐도 상관없지만 분류상 넣었다.

 

 

https://syerco0.tistory.com/9

다수의 점들을 각도에 따라 정렬하기

 

https://syerco0.tistory.com/10

백준 1708번 - 볼록 껍질

 

 

예제의 답을 보면서 힌트를 얻을 수도 있다.

 

왼쪽 아래의 점(사람마다 바뀔 수 있음)을 기준으로 해서

 

각도에 따라 정렬한 순서대로 점을 이어주면 선분끼리 겹치는 일이 없다는 것을 이용하면 된다.

 

직관적으로, 선분이 향하는 방향이 각도에 대해 일정한 방향이기 때문에

 

겹치지 않는다는 것을 생각할 수 있다.

 

 

여러 점이 한 직선 위에 있을 때는, 기준점에서 가까운 것부터 먼 것으로 이으면 겹치지 않는다.

 

한 가지 고려할 점은 있지만, 일단 패스하고 과정을 봐보자.

 

 

아무렇게나 찍은 점들이다.

 

이것들을 일단 위에서 소개한 과정으로 해보았다.

 

맨 왼쪽 아래가 시작이다.

 

 

빨간 선들은 위의 과정대로 했을 때 잘 나오는 것을 보여준다.

 

하지만 파란 선들을 보았을 때, 마지막 몇 개의 점이 직선을 이룰 경우에,

 

마지막 점과 첫 점을 잇는 선분이 중간에 다른 선과 겹치는 것을 볼 수 있다.

 

 

그래서 마지막 점의 경우는, 반대로 가야한다.

 

시작점, 마지막점과 CCW가 같은 점들은 정렬했을 때, 최후반부에 있을 것이기 때문에

 

마지막-1 번째 점부터 다시 검색해가면서 해당 점들의 순서를 뒤집어주면 된다.

 

 

그러면 마지막 선들이 겹치는 것을 막고 다각형을 만들 수 있다.

 

 

 

 

내 코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct D{
	int i,x,y;
};
D d[2020],mi;
int ccw(D a,D b,D c) {
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(D a,D b) {
	int c=ccw(mi,a,b);
	if(c==0) return abs(a.x-mi.x)+abs(a.y-mi.y)<abs(b.x-mi.x)+abs(b.y-mi.y);
	if(c>0) return 1;
	return 0;
}
int main() {
	int c,idx;
	cin>>c;
	while(c--) {
		int n;
		scanf("%d",&n);
		mi={-1,99999,99999};
		for(int i=0;i<n;i++) {
			scanf("%d %d",&d[i].x,&d[i].y);
			d[i].i=i;
			if(mi.y>d[i].y||(mi.y==d[i].y&&mi.x>d[i].x)) {
				mi={i,d[i].x,d[i].y};
				idx=i;
			}
		}
		swap(d[0],d[idx]);
		sort(d+1,d+n,cmp);
		int l;
		for(l=n-2;l>0;l--) if(ccw(d[0],d[l],d[n-1])!=0) break;
		l++;
		for(int i=l;i<(n+l+1)/2;i++) swap(d[i],d[n-i+l-1]);
		for(int i=0;i<n;i++) printf("%d ",d[i].i);
		printf("\n");
	}
}