BOJ 4181 | Convex Hull

컨벡스 헐이 제목인데 컨벡스 헐이 필요 없는 문제가 있다?

놀랍게도 이 문제를 푸는데 컨벡스 헐 알고리즘은 필요가 없다. 우리는 주어지는 점들을 정렬만 해주고 단순 다각형(#3679)에서 나왔던 마지막 직선상 점들만 정리해주면 된다.

코드

#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.first != b.first) return a.first < b.first;
	return a.second < b.second;
}

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.first != b.first) return a.first < b.first;
	return a.second < b.second;
}

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;
		char CT; cin >> CT;
		if (CT == 'N') continue;
		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());
	
	cout << dot.size() << endl;
	for (auto &i: dot){
		cout << i.first << ' ' << i.second << endl;
	}
	
}

int main(){
	FASTIO;
	solve();
}