취미로 코딩하기

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

이번에 볼 문제는 백준 7420번 문제인 맹독 방벽이다.
문제는 아래 링크를 확인하자.

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

주어진 점들을 모두 포함하는 가장 둘레가 짧은 다각형은 convex hull과 같다는 점을 떠올리자.

위와 같은 관찰에서 문제에서 구하는 방벽은 convex hull로부터 거리가 (convex hull의 바깥방향으로) L만큼 떨어진 폐곡선으로 나타남을 알 수 있다. 이 곡선의 길이는 (convex hull의 둘레) + (반지름이 L인 원의 둘레)와 같이 구할 수 있다는 점을 관찰하자.

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

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

int N; ll L;
pll points[100000];
vector<pll> upperhull; // leftmost x의 lowermost y부터 rightmost x의 uppermost y까지
vector<pll> lowerhull;

int CCW(pll& A, pll& B, pll& C) {
	ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
	if (ccw > 0) return 1;
	else if (ccw < 0) return -1;
	else return 0;
}

void andrew_algorithm() {
	sort(points, points + N);

	//upperhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = upperhull.size();
		while (cursize > 1) {
			auto& L = upperhull[cursize - 2], & M = upperhull[cursize - 1];
			if (CCW(L, M, cur) != -1) upperhull.pop_back(), cursize--;
			else break;
		}
		upperhull.emplace_back(cur);
	}

	//lowerhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = lowerhull.size();
		while (cursize > 1) {
			auto& L = lowerhull[cursize - 2], & M = lowerhull[cursize - 1];
			if (CCW(L, M, cur) != 1) lowerhull.pop_back(), cursize--;
			else break;
		}
		lowerhull.emplace_back(cur);
	}
}

ld ans, PI = acos(-1);

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

	cout << fixed;
	cout.precision(0);

	cin >> N >> L;
	for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;
	
	andrew_algorithm();

	for (int i = 0; i + 1 < upperhull.size(); i++) {
		ans += hypot(upperhull[i].first - upperhull[i + 1].first, upperhull[i].second - upperhull[i + 1].second);
	}

	for (int i = 0; i + 1 < lowerhull.size(); i++) {
		ans += hypot(lowerhull[i].first - lowerhull[i + 1].first, lowerhull[i].second - lowerhull[i + 1].second);
	}

	cout << ans + 2 * PI * L;
}