BOJ 15420 | Blowing Candles

쓰레기 슈트(#4225)와 비슷하지만 그 문제에는 없는 제한이 있다. 바로 $O(N^3)$으로도 풀 수 없고 $O(N^2)$으로 풀 수 없다는 것이다.

그러므로 회전하는 캘리퍼스를 이용해서 모든 직선에 대한 가장 먼 점의 거리를 구해서 $O(N)$에 해결해야 한다.

개인적으로는 이 문제의 티어가 #4225나 #15028과는 다르게 더 높게 책정되어야 한다고 생각한다. 이 문제만 회전하는 캘리퍼스까지 적용하기를 요구하기 때문이다.

코드

#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, R; cin >> N >> R;
	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]);
	}
	reverse(edges.begin(), edges.end());
	
	for (auto &i : edges) debug << i.x << ' ' << i.y << endl;
	
	int pa=0, pb=1, pc=1, pd=2;
	Dot a, b, c, d;
	a = edges[pa]; b = edges[pb]; c = edges[pc]; d = edges[pd];
	int flag = 0;
	double mnv = 999999999999;
	pair<ll, ll> d1, d2;
	while (!flag){
		//debug << "DBG " << dist << endl;
		if (ccw(a, b, {d.x-(c.x-b.x), d.y-(c.y-b.y)}) > 0){
			pc = (pc+1) % edges.size();
			pd = (pd+1) % edges.size();
		}
		else {
			double p1 = abs((a.x-b.x)*(b.y-c.y) - (b.x-c.x)*(a.y-b.y));
			double p2 = sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
			double dist = p1 / p2;
			if (mnv > dist && dist != 0){
				mnv = dist;
			}
			
			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];
	}
	
	printf("%.12lf", mnv);
}

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