[C++] 백준 7420번: 맹독방벽

문제 링크

7420번: 맹독방벽

문제 요약

자국 건물들의 좌표가 주어질 때, 자국민들을 보호하는 방벽을 지으려고 한다. 방벽은 자국의 모든 건물들로부터 L만큼 떨어져 있어야 한다. 이때, 방벽의 최소 길이를 구해야 한다.

접근 방법

자그마치 13개월 전에 풀다가 WA를 받고 까먹었다가 오늘 다시 잡은 문제입니다.

기본적으로 호를 제외한 직선 부분의 방벽 길이는 컨벡스헐을 구해서 해결하면 됩니다. 호를 계산하는 것도 생각보다 쉽다고 생각했습니다.

방벽의 각 호의 중심각은, 대응되는 내각의 크기를 $x$라고 할 때, $360^\circ - 180^\circ - x$입니다. 그리고 N각형의 내각의 합은 $180^\circ \times (N - 2)$입니다. 이를 이용해 모든 호의 중심각의 합을 구하면,

$360^\circ \times N - (180^\circ \times N) - (180^\circ \times (N - 2)) = 360^\circ$

이 된다고 생각했습니다. 따라서 컨벡스헐의 둘레의 길이를 구한 뒤에, 중심각이 $360^\circ$이고 반지름이 $L$인 원의 둘레의 길이, $2\pi L$만 더해주면 되는 간단한 문제라고 생각했습니다.

여기까지 쉽게 생각하고도 이전에 풀때는 볼록 다각형을 구할 때의 실수를 전혀 못찾아서 WA를 받았었습니다.

$\pi$는 아크코사인을 이용하면 쉽게 구할 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, l;
vector<pair<double, double>> v, res;

double ccw(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3) {
	double a = p1.first * p2.second + p2.first * p3.second + p3.first * p1.second;
	double b = p1.second * p2.first + p2.second * p3.first + p3.second * p1.first;
	return a - b;
}

bool compare1(const pair<double, double>& a, const pair<double, double>& b) {
	return (a.second == b.second ? a.first < b.first : a.second < b.second);
}

bool compare2(const pair<double, double>& a, const pair<double, double>& b) {
	double val = ccw(v[0], a, b);

	return (val ? val > 0 : compare1(a, b));
}

double dist(pair<double, double> a, pair<double, double> b) {
	return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> l;

	for (int i = 0; i < n; i++) {
		double x, y;
		cin >> x >> y;
		v.push_back({ x, y });
	}

	sort(v.begin(), v.end(), compare1);
	res.push_back(v[0]);

	sort(v.begin() + 1, v.end(), compare2);
	res.push_back(v[1]);

	for (int i = 2; i < n; i++) {
		while (res.size() >= 2) {
			auto p1 = res.back();
			res.pop_back();
			auto p2 = res.back();

			auto val = ccw(p2, p1, v[i]);

			if (val > 0) {
				res.push_back(p1);
				break;
			}
		}

		res.push_back(v[i]);
	}

	res.push_back(res[0]);

	double ans = 4 * acos(0) * l;
	for (int i = 0; i < res.size() - 1; i++)
		ans += dist(res[i], res[i + 1]);

	cout << round(ans) << '\n';
	return 0;
}