[BOJ 10903 // C++] Wall construction

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10903번 문제인 Wall construction이다.
문제는 아래 링크를 확인하자.

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

 

모든 기둥의 반지름이 동일하므로, 구하고자 하는 벽의 모양은 주어진 기둥의 중심을 모두 포함하는 최소볼록다각형(convex hull)으로부터 도형의 바깥쪽으로 $R$만큼 떨어진 점들을 모두 포함하는 모양을 이루게 된다.

 

위 도형의 둘레의 직선부는 convex hull의 길이와 같고 곡선부는 모두 합치면 반지름이 $R$인 원의 둘레가 됨을 관찰하자.

 

이를 이용하면 convex hull을 구해 각 변의 길이와 원의 둘레의 길이를 합하는 것으로 문제의 답을 구할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

ll CCW(pll p1, pll p2, pll p3) {
	return p1.first * p2.second + p2.first * p3.second + p3.first * p1.second
	-p1.second * p2.first - p2.second * p3.first - p3.second * p1.first;
}

int N, R;
pll P[1000];
int usize, lsize;
vector<pll> uhull, lhull;

void chull() {
	for (int i = 0; i < N; i++) {
		while (uhull.size() > 1) {
			if (CCW(uhull[uhull.size() - 2], uhull.back(), P[i]) <= 0) uhull.pop_back();
			else break;
		}
		uhull.emplace_back(P[i]);
	}
	for (int i = 0; i < N; i++) {
		while (lhull.size() > 1) {
			if (CCW(lhull[lhull.size() - 2], lhull.back(), P[i]) >= 0) lhull.pop_back();
			else break;
		}
		lhull.emplace_back(P[i]);
	}
}

ld ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> R;
	for (int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;
	sort(P, P + N);
	chull();

	usize = uhull.size();
	for (int i = 0; i + 1 < usize; i++) ans += hypot((ld)(uhull[i + 1].first - uhull[i].first), (ld)(uhull[i + 1].second - uhull[i].second));
	lsize = lhull.size();
	for (int i = 0; i + 1 < lsize; i++) ans += hypot((ld)(lhull[i + 1].first - lhull[i].first), (ld)(lhull[i + 1].second - lhull[i].second));
	ans += acos((ld)-1) * R * 2;

	cout << fixed;
	cout.precision(12);
	cout << ans;
}