BOJ 7420 맹독 방벽

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

문제

화학 제국의 왕 성준이는 계속되는 이웃나라의 침범으로부터 자유로워지기 위해 자국의 자랑 화학 방벽을 건설하기로 마음먹었다. 이 방벽은 근처에 다가오는 생명체에게 해로운 독성을 내뿜어서 더이상 다른 나라들이 얼씬도 못하게 만들 것이다!

그러나 이 방벽은 만들기 까다롭기에 가능한 한 적게 지어야 하며, 자국민들에게도 악영향을 끼칠 수 있으므로 자국의 모든 건물들로부터 L 이상의 거리를 유지해야만 한다.

자국의 건물들의 좌표가 주어졌을 때, 모든 건물들로부터 L 이상의 거리를 두면서 모든 건물을 한번에 두르는 방벽의 최소 길이를 구하시오.

입력

첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수)

다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌표는 다르며, 건물은 충분히 작아서 점과 같다고 생각해도 좋다. 방벽은 자신들끼리 교차해서는 안 되며 끊어져서도 안 된다.

풀이

자명하게, 맹독 방벽은 건물들의 Convex Hull보다 L이상 떨어져 있어야 한다.

Convex Hull에서 L만큼 떨어진 점들을 모두 모은 폐곡선의 길이를 생각해보자.

Convex Hull에서 L 만큼 떨어진 점들은 Convex Hull을 이루는 선분을 바깥으로 L만큼 평행이동한 부분(위 그림의 검은 선분)을 포함하고, 나머지 부분은 꼭짓점에서 L만큼 떨어진 호(위 그림의 붉은 곡선)가 된다. 이때 검은 선분의 길이 총합은 Convex Hull의 둘레와 같고, 붉은 곡선은 모든 방향의 partition이므로(검은 선분의 양 끝과 Convex Hull의 꼭짓점을 이으면 직사각형이 되고, 평행사변형이므로 붉은 두 선분은 서로 평행하기 때문) 반지름 L인 원의 원주가 된다.

Convex Hull을 찾아 둘레를 구하고, L에 3.1415926*2를 곱한 값을 더해 답을 얻을 수 있다.