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

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

3679번: 단순 다각형

---

Solved By: Convex Hull, Geometry

 

이번 문제는 Convex Hull을 구하는 문제가 아닙니다. 주어진 모든 점을 사용하기 때문에 Convex Hull을 구하면서 누락된 점이 있으면 안 됩니다. Convex Hull을 구하기 직전까지의 정렬을 구하면 원하는 답을 찾을 수 있습니다. 시작점과 시작점을 기준으로 CCW를 하여 반시계 방향으로 정렬합니다.

 

하지만, 한 가지 예외 케이스가 있습니다.

문제에서 시작점 기준은 다르지만 노란색으로 동그라미 친 곳을 v[0]라고 하겠습니다.

그리고, 빨간색으로 동그라미 친 부분들은 v[0]에서 직선을 그었을 때, 모두 한 직선 위에 있는 점들입니다.

 

아래 오른쪽 빨간 동그라미 부분은 정렬했을 때, 문제가 없습니다. 왜냐하면 정렬할 때, 한 직선 위에 있다면 즉, CCW값이 0이라면 거리가 가까운 순으로 정렬을 했기 때문입니다.

 

하지만, 왼쪽 윗 부분 빨간 동그라미에 있는 점들을 거리가 가까운 순으로 정렬한다면 다각형의 점들 순서로써는 옳지 않은 답입니다. 반대로 뒤집혀 있어야 순서가 맞으니까요.

 

그래서 이번 문제의 핵심은 정렬을 한 뒤, 끝점에서 끝점 직전의 점이 v[0]을 기준으로 한 직선 위에 있다면 뒤집어주는 것이 포인트였습니다. 그리고, 한 직선 위에 여러 점이 있다면 그 직선 위의 모든 점들을 뒤집어주는 것은 당연합니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#define ll long long
using namespace std;

struct Point{
    ll y, x;
    int p;
};

vector<Point> v;

ll dist(Point a, Point b){
    return sqrtl(powl(a.x - b.x, 2) + powl(a.y - b.y, 2));
}

ll ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(Point a, Point b){
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

bool cmp2(Point a, Point b){
    ll temp = ccw(v[0], a, b);
    if(temp == 0){
        return dist(v[0], a) < dist(v[0], b);
    }
    
    return temp > 0;
}

int main(){
    int c;
    cin >> c;
    
    for(int C = 0; C < c; C++){
        int n; cin >> n;
        v.clear();
        for(int i = 0; i < n; i++){
            ll a, b; cin >> a >> b;
            v.push_back({b, a, i});
        }
        
        sort(v.begin(), v.end(), cmp);
        sort(v.begin() + 1, v.end(), cmp2);
        
        //auto pgn = convexHull();
        
        // 핵심
        int pt = v.size() - 1;
        
        for(int i = v.size() - 1; i >= 1; i--){
            if(ccw(v[0], v[pt], v[pt - 1]) == 0) pt--;
            else break;
        }
        
        reverse(v.begin() + pt, v.end());
        
        for(int i = 0; i < v.size(); i++){
            cout << v[i].p << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}