[BOJ] 백준 4225. 쓰레기 슈트 (Platinum III)

클래스에 있길래 풀어본 문제.

문제는 아래와 같다.

https://www.acmicpc.net/problem/4225

4225번: 쓰레기 슈트

---

의식의 흐름 및 해설

예제입력을 보고 각 점에서 직선까지의 거리를 구해야되겠다는 생각이 들었다.

이 때, 직선은 슈트의 변을 의미하며, 변과 점까지의 거리 중 최댓값을 찾는다.

다른 변에서도 최댓값을 찾고, 그 최댓값들 중 최솟값을 출력해주면 되는 문제라 생각이 됐다.

N이 작기 때문에 시간복잡도 상으로 문제되진 않는다.

 

다만, 오목다각형일 경우는 점과 직선사이의 거리가 가로질러서 측정이 돼버리기 때문에 성립하지 않으므로 볼록 껍질을 구해준 후 위 과정을 처리해야 한다. stack을 이용하여 convex hull을 구해준 후, 점과 직선사이의 거리를 구해준다.

---

시행착오

• 여러 개의 테스트케이스 내에서 점의 x, y좌표 초기화는 잘 이루어졌으나, 점끼리 x, y좌표의 차이는 초기화를 해주지 않아서 엄청난 횟수의 맞왜틀을 하였다.
• 0.005를 더해도 괜찮긴 한 듯하나, 부동소수점 오차가 발생할 수 있으므로 0.004999999를 더해주었다.

https://www.acmicpc.net/board/view/77001

글 읽기 - 스트레스로 화병날 것 같습니다 ㅠㅠ 소수오차 관련으로 틀리는 것 같습니다.

고수님들께서 내 코드를 돌려봐주신 듯하다. 정말 감사합니다.

엄청난 맞왜틀의 흔적이 보이는가...

굉장히 힘들었다.

처음엔 소수 오차로 틀리는 줄 알았으나, 초기화 문제로 틀린 것이었다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 103;
const double INF = 0x3f3f3f3f;
const double EPS = 1e-12;
const int LNF = 1e18;
const int MOD = 1e9 + 7;
int t, N;
struct Point {
	double x, y, p, q;
	Point() {}
	Point(double x1, double y1, double p1 = 0, double q1 = 0)
		:x(x1), y(y1), p(p1), q(p1) {}
	bool operator<(const Point& O) {
		if (q * O.p != p * O.q)
			return q * O.p < p* O.q;
		if (y != O.y)
			return y < O.y;
		return x < O.x;
	}
};
Point a[MAX];
double ccw(const Point& p1, const Point& p2, const Point& p3) {
	return (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y)
		- (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	while (cin >> N && N) {
		double ans = INF;
		for (int i = 0; i < N; i++) {
			a[i] = { 0,0,0,0 };
			cin >> a[i].x >> a[i].y;
		}
		swap(a[0], *min_element(a, a + N));
		for (int i = 1; i < N; i++) {
			a[i].p = a[i].x - a[0].x;
			a[i].q = a[i].y - a[0].y;
		}
		sort(a + 1, a + N);
		stack<int> S;
		S.push(0);
		S.push(1);
		for (int i = 2; i < N; i++) {
			while (S.size() >= 2) {
				int second = S.top();
				S.pop();
				int first = S.top();
				if (ccw(a[first], a[second], a[i]) > 0) {
					S.push(second);
					break;
				}
			}
			S.push(i);
		}
		vector<Point> hull(S.size());
		for (int i = 0; i < hull.size(); i++) {
			hull[i] = a[S.top()];
			S.pop();
		}
		int n = hull.size();
		for (int i = 0; i < n; i++) {
			double A, B, C, res = 0;
			if (hull[i].x == hull[(i + 1) % n].x) {
				for (int j = 0; j < n; j++) {
					res = max(res, abs(hull[i].x - hull[j].x));
				}
				ans = min(ans, res);
				continue;
			}
			A = (hull[(i + 1) % n].y - hull[i].y) / (hull[(i + 1) % n].x - hull[i].x);
			B = -1;
			C = hull[i].y - A * hull[i].x;
			for (int j = 0; j < n; j++) {
				res = max(res, abs(A * hull[j].x + B * hull[j].y + C)
					/ sqrt(A * A + B * B));
			}
			ans = min(ans, res);
		}
		cout << fixed;
		cout.precision(2);
		cout << "Case " << ++t << ": " << ans + 0.00499999 << "\n";
	}
}

---

풀이는 어렵지 않았지만, 꽤나 고통스러웠던 문제.

개인적으로 여러개의 테스트케이스, 기하학, 소수점출력 문제를 실수유발 여지가 있어 싫어하는 편인데,

이 문제는 세개가 짬뽕돼있어서 그런지 너무 고통스러웠다 ㅠㅠ