BOJ 15028 | Breaking Biscuits

= 쓰레기 슈트 (#4225)
https://velog.io/@bformat/BOJ-4225-%EC%93%B0%EB%A0%88%EA%B8%B0-%EC%8A%88%ED%8A%B8

코드

#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 x, y;
};

vector<Dot> dot;

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

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

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

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});
	}
	sort(dot.begin(), dot.end(), cmp);
	fx = dot[0].x; fy = dot[0].y;
	
	sort(dot.begin()+1, dot.end(), _cmp);
	
	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++;
	}
	vector<Dot> edges;
	while (!task.empty()){
		int tmp = task.top(); task.pop();
		edges.push_back(dot[tmp]);
	}
	
	for (auto &i : edges) debug << i.x << ' ' << i.y << endl;
	
	double mindist = 9999999.0;
	int sz = edges.size();
	for (int i = 0; i < sz; i++){
		double mdist = 0;
		Dot cur = edges[i];
		Dot next = edges[(i+1)%sz];
		for (int j = i+2; j < sz+i; j++){
			double p1 = abs((next.x-cur.x)*(cur.y-edges[j%sz].y) - (cur.x-edges[j%sz].x)*(next.y-cur.y));
			double p2 = sqrt((next.x-cur.x)*(next.x-cur.x)+(next.y-cur.y)*(next.y-cur.y));
			double dist = p1 / p2;
			//debug << dist << endl;
			if (mdist < dist) mdist = dist;
		}
		if (mindist > mdist) mindist = mdist;
	}
	
	printf("%.12lf", mindist);
}

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