백준 3679 (C++) 단순 다각형

최초 업로드: 2025-08-15 21:31:59

최근 수정 시간: 2025-08-15 21:32:23

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] 단순 다각형

[문제 링크](https://www.acmicpc.net/problem/3679)

## 문제 설명

평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다.

예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다.

항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러 가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치에 있는 경우는 없으며, 모든 점이 한 직선위에 있는 경우는 없다.

## 입력

첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌표 x와 y이며, 좌표는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

## 출력

각 테스트 케이스마다 0부터 n-1까지 순열중 하나를 출력해야 한다. 출력하는 순열은 입력으로 주어지는 점의 번호를 나타내며, 출력하는 순서대로 점을 이었을 때, 올바른 다각형을 만들어야 한다.

## 풀이
#### 그라함 스캔을 하기 전에 각도 정렬 하던 것에서 맨 뒤 점들이 기준점에 일자로 놓인 경우만 예외 처리 해주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

struct point {
 int x, y, idx, p=0, q=0;
 bool operator<(const point o) const {
 if(p*o.q!=q*o.p) return p*o.q > q*o.p;
 if(y!=o.y) return y < o.y;
 return x < o.x;
 }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int c; cin >> c;
 while(c--) {
 int n; cin >> n;
 vector<point> v(n);
 for(int i=0;i<n;i++) {
 cin >> v[i].x >> v[i].y;
 v[i].idx = i;
 }
 sort(v.begin(), v.end());

for(int i=1;i<n;i++) {
 v[i].p = v[i].x-v[0].x;
 v[i].q = v[i].y-v[0].y;
 }
 sort(v.begin(), v.end());

/** 
         * 시게 반대 방향으로 도형을 연결하는 경우
         * y 좌표가 큰 점에서 작은 점으로 연결할 때
         * 세 점 이상이 기준점에서 일직선으로 연결되는 경우 거꾸로 연결됨 (기준점에서의 벡터가 똑같기에 좌표로 오름차순으로 정렬됨)
         */
        for(int i=n-2;i>=0;i--) {
            if(v[i].p*v[n-1].q!=v[i].q*v[n-1].p) {
                reverse(&v[i+1], &v[n]);
                break;
            }
        }

for(int i=0;i<n;i++) cout << v[i].idx << ' ';
 cout << '\n';
 }
}
```