백준 7420 (C++) 맹독 방벽

최초 업로드: 2025-08-12 17:08:12

최근 수정 시간: 2025-08-12 17:08:39

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] 맹독 방벽

[문제 링크](https://www.acmicpc.net/problem/7420)

## 문제 설명

<img alt="" src="https://upload.acmicpc.net/e8b1d57d-ee8e-4e2d-bf2b-6e788776c553/-/preview/" style="margin-left: 10px; float: right;">화학 제국의 왕 성준이는 계속되는 이웃나라의 침범으로부터 자유로워지기 위해 자국의 자랑 화학 방벽을 건설하기로 마음먹었다. 이 방벽은 근처에 다가오는 생명체에게 해로운 독성을 내뿜어서 더이상 다른 나라들이 얼씬도 못하게 만들 것이다!

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

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

## 입력

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

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

## 출력

첫째 줄에 답을 정수 단위로 반올림하여 출력한다.

## 풀이
#### 직선 길이의 합은 볼록 다각형의 둘레 길이, 곡선 길이의 합은 반지름이 L인 원의 둘레라는 사실을 쉽게 알 수 있습니다. 이를 그라함 스캔으로 구하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const double PI = atan(1)*4;

int n, l;

struct pos {
 ll x, y, p=0, q=0;
 bool operator<(const pos o) const {
 if(p*o.q!=q*o.p) return p*o.q > q*o.p;
 if(y!=o.y) return y < o.y;
 return x < o.x;
 }
};

ll ccw(pos a, pos b, pos c) {
    pos vec1 = {b.x-a.x, b.y-a.y};
    pos vec2 = {c.x-a.x, c.y-a.y};
    return vec1.x*vec2.y - vec1.y*vec2.x;
}

ll getRes(vector<pos> stk) {
 double ret = l*2*PI;
 for(int i=0;i<stk.size();i++) {
 ret += sqrtl(pow(stk[i].x-stk[(i+1)%stk.size()].x, 2)+pow(stk[i].y-stk[(i+1)%stk.size()].y, 2));
 }
 return round(ret);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> l;
 vector<pos> v(n);
 for(int i=0;i<n;i++) cin >> v[i].x >> v[i].y;
 sort(v.begin(), v.end());
 for(int i=0;i<n;i++) {
 v[i].p = v[i].x - v[0].x;
 v[i].q = v[i].y - v[0].y;
 }
 sort(v.begin(), v.end());

vector<pos> stk;
 for(int i=0;i<n;i++) {
 while(stk.size()>=2 && ccw(stk[stk.size()-2], stk[stk.size()-1], v[i])<=0) stk.pop_back();
 stk.push_back(v[i]);
 }
 cout << getRes(stk);
}
```