[백준] 3679 - 단순 다각형

문제

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

 

풀이

오랫만에 보는 Convex hull...? 비슷한 문제

원래는 스택에 하나씩 push/pop하면서 Convex hull을 구해줘야하는데, 이는 모든 점을 사용해서 다각형을 만들어 주기만 하면 된다.

 

시작점0을 기준으로 반시계 기준으로 정렬하고 점을 차례로 이으면 좌측(N=5)그림과 같이 다각형을 그릴 수 있다.

하지만 우측(N=7)그림과 같이 마지막 점들이 직선을 이루고 있는 경우 역순으로 이어줘야한다.

이경우만 잘 고려해서 cross(0, N - 1, index)가 0일 경우부터는 역순으로 이어주면된다.

좌 / 우

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <stack>
using namespace std;
struct Dot {
    int x, y;
    bool operator<(const Dot& o) const {
        if (x < o.x) return true;
        else if (x > o.x) return false;
        return y < o.y;
    }
};
vector<Dot> v;
int N, T;
vector<Dot> answer;
map<Dot, int> indexMap;
int cross(Dot a, Dot b, Dot c)
{
    // a > b > c
    Dot l1 = { b.x - a.x, b.y - a.y };
    Dot l2 = { c.x - b.x, c.y - b.y };
    int r = l1.x * l2.y - l1.y * l2.x;
    if (r < 0) return -1;
    else if (r > 0) return 1;
    return 0;
}
int getDistance(Dot a)
{
    return (v[0].x - a.x) * (v[0].x - a.x) + (v[0].y - a.y) * (v[0].y - a.y);
}
bool cmp(Dot a, Dot b) {
    int r = cross(v[0], a, b);
    if (r > 0) return 1;
    else if (r == 0) return getDistance(a) < getDistance(b);
    return 0;
}
void solve()
{
    v.clear();
    indexMap.clear();
    answer.clear();
    cin >> N;
    int a, b, ta, tb;
    cin >> a >> b;
    v.push_back({ a, b });
    for (int i = 1; i < N; ++i) {
        //dot save
        //가장 x,y가 작은 시작 점 찾기
        cin >> a >> b;
        indexMap[{a, b}] = i;
        if (a < v[0].x) {
            ta = v[0].x;
            tb = v[0].y;
            v[0] = { a, b };
            v.push_back({ ta, tb });
        }
        else if (a == v[0].x && b < v[0].y) {
            ta = v[0].x;
            tb = v[0].y;
            v[0] = { a, b };
            v.push_back({ ta, tb });
        }
        else {
            v.push_back({ a, b });
        }
    }

    // 반시계 정렬
    sort(v.begin() + 1, v.end(), cmp);
    answer.push_back(v[0]);
    answer.push_back(v[1]);
    int rflag = 0;
    for (int i = 2; i < v.size() - 1; ++i) {
        if (cross(v[0], v[v.size() - 1], v[i]) == 0) {
            for (int j = v.size() - 1; j >= i; --j) {
                answer.push_back(v[j]);
            }
            rflag = 1;
            break;
        }
        answer.push_back(v[i]);
    }
    if (rflag == 0) answer.push_back(v[v.size() - 1]);
    for (int i = 0; i < answer.size(); ++i) {
        cout << indexMap[answer[i]] << " ";
    }
    cout << "\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    for (int i = 0; i < T; ++i) solve();
    return 0;
}