BOJ 3679 | 단순 다각형

Convex Hull을 구할 필요는 없고, 전처리 과정이었던 그라함 정렬만 해주면 된다.

다만 나도 몇번 틀렸던 부분이 있는데, 정렬 과정에서 시작과 끝 몇개의 점이 직선상에 놓인 경우를 생각해보자.

이런 상황에서 거리를 기준으로 가까이 있는 것부터 계산하도록 정렬하는게 Convex Hull을 구할 때는 맞다.

그러나 이 문제에서는 점들을 순회하면서 마지막에 시작점으로 돌아와야 하기 때문에 마지막 직선상 점은 멀리 있는 것부터 순회해야 한다.

따라서 정렬 이후 이 부분만 처리해주면 된다.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define ll long long
#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

ll fx, fy;
struct Dot{
	ll first, second;
	ll idx;
};

vector<Dot> dot;

bool cmp(Dot a, Dot b){
	if (a.second != b.second) return a.second < b.second;
	return a.first < b.first;
}

bool _cmp(Dot a, Dot b){
	ll l = (b.first - fx) * (a.second - fy);
	ll r = (a.first - fx) * (b.second - fy);
	if (l != r) return l < r;
	
	if (a.second != b.second) return a.second < b.second;
	return a.first < b.first;
}

ll ccw(Dot a, Dot b, Dot c){
	return (b.first-a.first)*(c.second-b.second)-(c.first-b.first)*(b.second-a.second);
}

void solve(){
	int N; cin >> N;
	dot.clear();
	for (int i = 0; i < N; i++){
		ll x, y; cin >> x >> y;
		dot.push_back({x, y, i});
	}
	sort(dot.begin(), dot.end(), cmp);
	fx = dot[0].first; fy = dot[0].second;
	
	sort(dot.begin()+1, dot.end(), _cmp);
	
	int pt = dot.size()-1;
	for (int i = pt; i >= 1; i--){
		if (ccw(dot[0], dot[pt], dot[pt-1]) == 0) pt--;
		else break;
	}
	reverse(dot.begin() + pt, dot.end());
	
	for (auto &i: dot){
		cout << i.idx << ' ';
	}
	cout << endl;
	
}

int main(){
	FASTIO;
	int T; cin >> T;
	for (int i = 0; i < T; i++){
		solve();
	}
}