BOJ 4225 | 쓰레기 슈트

이 문제는 Convex Hull 없이도 풀리는 문제다.
N이 최대 100이기 때문에 모든 점에 대해 검사하는 $O(N^3)$으로 충분히 풀린다.

그러나 N을 조금 늘리기만 해도 이 방법은 통하지 않으므로 볼록 껍질을 구해서 $O(N^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;
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, int Q){
	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("Case %d: %.2lf\n", Q, ceil(mindist*100)/100.0);
}

int main(){
	FASTIO;
	int cnt = 1;
 	while (true){
 		int N; cin >> N;
 		if (N==0) break;
 		solve(N, cnt++);
	}
}

그렇지만 어쨌든 이 문제는 $O(N^3)$으로도 해결이 되기 때문에 그 코드도 올려보겠다.

$O(N^3)$ 코드

#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'

struct Dot{
	ll x, y;
};

vector<Dot> dot;

void solve(int N, int Q){
	dot.clear();
	for (int i = 0; i < N; i++){
		ll x, y; cin >> x >> y;
		dot.push_back({x, y});
	}
	
	double mindist = 9999999.0;
	int sz = dot.size();
	for (int i = 0; i < sz; i++){ for (int k = 0; k < sz; k++){
		if (i==k) continue;
		double mxdist = 0.0;
		double mndist = 0.0;
		Dot cur = dot[i];
		Dot next = dot[k];
		for (int j = 0; j < sz; j++){
			if (j==i || j==k) continue;
			double p1 = (next.x-cur.x)*(cur.y-dot[j].y) - (cur.x-dot[j].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 (mxdist < dist) mxdist = dist;
			if (mndist > dist) mndist = dist;
		}
		if (mindist > mxdist-mndist) mindist = mxdist-mndist;
	}}
	
	printf("Case %d: %.2lf\n", Q, ceil(mindist*100)/100.0);
}

int main(){
	FASTIO;
	int cnt = 1;
 	while (true){
 		int N; cin >> N;
 		if (N==0) break;
 		solve(N, cnt++);
	}
}