BOJ 9240 | 로버트 후드

딱 봐도 고속도로(#10254) 하위호환이다.
https://velog.io/@bformat/BOJ-10254-%EA%B3%A0%EC%86%8D%EB%8F%84%EB%A1%9C

이렇게 날로 먹을 수 있는 문제들이 너무 많다.
고속도로(#10254)와 차이점은 마지막 점 2개의 거리를 구해야 한다는 것이다. 이것만 조심해서 제출하자.

코드

#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;
vector<pair<ll, ll>> dot;
vector<pair<ll, ll>> edges;

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

bool _cmp(pair<ll, ll> a, pair<ll, ll> 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(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> 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});
	}
	stable_sort(dot.begin(), dot.end(), cmp);
	fx = dot[0].first; fy = dot[0].second;
	
	stable_sort(dot.begin()+1, dot.end(), _cmp);
	
	//for (auto &i : dot) debug << i.first << ' ' << i.second << endl;
	stack<int> task;
	task.push(0);
	task.push(1);
	
	
	int next = 2;
	while (next < N){
		while (task.size() >= 2){
			ll A, B;
			B = task.top(); task.pop();
			A = task.top();
			
			// if ccw(A, B, next) > 0 => B is edge
			if (ccw(dot[A], dot[B], dot[next]) > 0){
				task.push(B);
				break;
			}
		}
		task.push(next);
		next++;
	}
	
	//cout << task.size() << endl;
	
	edges.clear();
	while (!task.empty()){
		int t = task.top(); task.pop();
		edges.push_back({dot[t].first, dot[t].second});
	}
	reverse(edges.begin(), edges.end());
	
	
	//rotating callipers
	pair<ll, ll> a, b, c, d;
	
	/*ll mnx = edges[0].first, mxx = edges[0].first;
	ll mni = 0, mxi = 0;
	for (int i = 0; i < edges.size(); i++){
		if (mnx >= edges[i].first){
			mnx = edges[i].first;
			mni = i;
		}
		if (mxx <= edges[i].first){
			mxx = edges[i].first;
			mxi = i;
		}
	}*/
	
	int pa=0, pb=1, pc=1, pd=2;
	a = edges[pa]; b = edges[pb]; c = edges[pc]; d = edges[pd];
	int flag = 0;
	double mxv = 0;
	pair<ll, ll> d1, d2;
	while (!flag){
		double dist = sqrt((c.first - a.first)*(c.first - a.first) + (c.second - a.second)*(c.second - a.second));
		//debug << "DBG " << dist << endl;
		if (mxv <= dist){
			mxv = dist;
			d1 = a; d2 = c;
			//debug << "UPDATE " << dist << endl;
			//debug << d1.first << ' ' << d1.second << ' ' << d2.first << ' ' << d2.second << endl;
		}
		
		if (ccw(a, b, {d.first-(c.first-b.first), d.second-(c.second-b.second)}) > 0){
			pc = (pc+1) % edges.size();
			pd = (pd+1) % edges.size();
		}
		else {
			pa = (pa+1) % edges.size();
			pb = (pb+1) % edges.size();
			if (pa == 0) flag++;
		}
		a = edges[pa]; b = edges[pb]; c = edges[pc]; d = edges[pd];
	}
	
	double dx = d1.first - d2.first;
	double dy = d1.second - d2.second;
	printf("%.8lf", sqrt(dx*dx+dy*dy));
	
}

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