백준 7420번 - 맹독 방벽

 

 

* 문제 링크

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

7420번: 맹독 방벽

 

 

 

 

문제 내용 요약

 

 

화학 제국의 왕 성준이가 타국의 공격을 막으려고 건물들 ( 3 ≤ L ≤ 1000 ) 을 감싸는 맹독 방벽을 세우려 한다.

 

근데 만들기 힘들어서 최대한 적게, 그리고 자국민들 피해 안 가게 하려고

 

건물들에서 최소 L ( 1 ≤ L ≤ 1000 ) 만큼 떨어지게, 모든 건물을 한 번에 두르게 지으면 길이가 얼마나 될까?

 

 

 

 

 

접근법

 

 

* Convex Hull 에 대한 설명은 아래의 글 참조

 

https://syerco0.tistory.com/10

백준 1708번 - 볼록 껍질

 

기본적으로 Convex Hull 을 이용하여 외곽의 길이를 구하게 될텐데,

 

추가되는 것은, 꼭짓점 부분에 호로 만드는 방벽의 길이다.

 

 

파란 점들은 내부 점, 빨간(노란색과 겹쳐버린) 점들이 컨벡스 헐을 이루는 점들이며, 검은 선이 방벽이다.

 

일일이 저 호의 길이를 구하는 방법을 사용하는 것은 가능하다.

 

다만 그렇게 귀찮은 방법을 쓰지 않고도 구하는 방법이 있으니, 우리는 그것을 이용할 것이다.

 

 

일단 컨벡스 헐을 이루는 점에서 수직으로 선을 그었을 때 (노란 선),

 

검은 직선은 각각의 대응되는 빨간 직선(껍질의 선분)과 길이가 같다.

 

 

n개의 꼭짓점으로 이루어진 볼록 껍질에 대해

 

검은 곡선은 호의 형태를 이루고, 호의 각도를 각각 <a_1, <a_2 ... 로 나타내고

 

꼭짓점을 맞대고 있는 볼록 껍질의 해당 내부각을 <b_1, <b_2 ... 로 나타내었을 때,

 

 

앞에&nbsp;&there4; 붙이는 걸 까먹고 저장 안 해버렸다. 수정하기 귀찮았다.

 

즉, 반지름이 L 인 원의 길이와 같다.

 

 

결론적으로, 컨벡스 헐을 구한 후, 그것의 둘레 길이와 반지름이 L인 원의 길이를 더한 값이 방벽의 길이가 된다.

 

 

 

 

내 코드

#include <iostream>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
using namespace std;
struct D{
	long long x,y;
};
D d[1010],mi={99999,99999},s[1010];
long long ccw(D a,D b,D c) {
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(D a,D b) {
	long long n=ccw(d[0],a,b);
	if(n==0) return (abs(a.x-d[0].x)+abs(a.y-d[0].y))<(abs(b.x-d[0].x)+abs(b.y-d[0].y));
	if(n>0) return 1;
	return 0;
}
double dist(D a,D b) {
	double n=double((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
	return sqrt(n);
}
int main() {
	int n,idx,l;
	cin>>n>>l;
	for(int i=0;i<n;i++) {
		scanf("%lld %lld",&d[i].x,&d[i].y);
		if(d[i].y<mi.y||(d[i].y==mi.y&&d[i].x<mi.x)) {
			mi={d[i].x,d[i].y};
			idx=i;
		}
	}
	swap(d[0],d[idx]);
	sort(d+1,d+n,cmp);
	s[0]=d[0];
	s[1]=d[1];
	idx=2;
	for(int i=2;i<n;i++) {
		while(idx>1&&ccw(s[idx-2],s[idx-1],d[i])<=0) idx--;
		s[idx++]=d[i];
	}
	double r=0;
	for(int i=1;i<idx;i++) {
		r+=dist(s[i-1],s[i]);
	}
	r+=dist(s[0],s[idx-1])+(double)2*(double)l*M_PI;
	cout<<round(r);
}

 

 

 

여담

 

cmp 함수의 내부 n==0 일 때, 기준 점을 원점으로 생각하여 비교할 점들을 평행이동하여 정렬해줘야 하는데

 

평행이동하는 걸 까먹고 실수 오차 문제인 줄 알고 10번인가 삽질을 해버렸다.

 

도저히 안 보여서 질문을 올린 후 약 30분 정도였나 뒤에 봤는데

 

한 분이 반례를 주셨고, 덕분에 문제를 찾을 수 있었다.

 

감사합니다.

 

 

 

그리고 이걸 못 보네 이녀석