Boj #4225 쓰레기 슈트(Platinum III)

쓰레기 슈트는 convex hull 알고리즘을 활용하는 문제이다. 이 글에서는 convex hull 알고리즘을 다루지 않으니, 

이에 대해서는 다른 글을 읽고 오길 추천한다.

 

쓰레기 슈트 문제는, 주어진 점들로 이루어진 다각형이 있을 때, 이를 회전시켜 들어갈 수 있도록 하는 구멍의 최소 너비를

찾는 문제이다(문제 설명에 쓰여 있다). 그리고, 이 문제의 AC 여부를 결정하는 가장 큰 요소는... 부동소수점.

항상 부동소수점 오차를 주의하고, 반올림 함수나 올림 함수 등을 컴퓨터에 미리 구현해 놓고 필요시마다 가져다 쓰는 것도 나쁘지 않은 방법이다(실제로 본인은 그렇게 했다).

 

쓰레기 슈트 문제는 얼핏 보기에는 컨벡스 헐을 사용하는 문제가 아닌 듯 보일 때도 있다. 그러나, 풀이에 사용할 가정이 성립하려면 convex hull이어야 한다. 문제를 관통하는 정리는 다음과 같다:

 

한 점과, convex hull의 한 변 사이에 모든 점들이 놓이도록 하는 점과 변을 잡자. 이들 사이의 거리 중 최솟값이 구멍의 너비이다.

점과 직선 사이에 놓이는 점들의 예시(다소 말만으로는 이해하기 어려울 수 있기에 그림으로 대체한다).

 

이는 어찌 보면 당연한 소리다. convex hull이 구멍에 들어갈 때, 한 변과 한 점에서 각각 구멍과 접하기 때문이다. 두 점이 각각 접한다 하면, 항상 이보다 짧은 점과 직선 사이의 거리가 존재하고, 이들 내부에 모든 점이 포함(가정에서)되므로, 구멍은 더 작아질 수 있다.

여기에서 의문이 생긴다: 그렇다면 모든 점들이 내부에 놓이는 지는 어떻게 아는가?

여기에서 convex hull이라는 가정을 이용하여 판단한다.

.

가장 쉽게 생각할 수 있는 방법은 고른 점과 직선 위의 두 점을 제외한 점들과 직선 사이의 거리를 모두 재고, 이들이 모두 고른 점과 직선 사이의 거리보다 짧으면 점과 직선 사이에 모든 점이 있다 판단하는 것이다.

이 방법에는 convex hull이 필요하다. 위 예시를 보자. convex hull이 아니면, 한 변을 기준으로 양쪽에 점이 존재하여 잘못된 비교 판단(부호에 따른)을 할 수 있다. 그러나, convex hull이면 한 직선을 기준으로 한쪽에만 점이 있다는 것이 보장된다(볼록다각형이므로). 귀찮아지는 예외 case를 처리하기 위해 어쩌면 convex hull이라는 방법을 사용한 것이다.

 

이렇게 판정한 뒤, 부동소수점 오차를 잘 고려해서 짠 코드는 다음과 같다:

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<pair<ll, ll>> ans;
pair<ll, ll> v[100001];
int cnt;
ll xmax, ymax, T;
ll CCW(pair<ll, ll> &x1, pair<ll, ll> &x2, pair<ll, ll> &x3){
	pair<ll, ll> v1={x2.first-x1.first, x2.second-x1.second};
	pair<ll, ll> v2={x3.first-x1.first, x3.second-x1.second};
	return v1.first*v2.second-v2.first*v1.second;
}
bool ycomp(pair<ll, ll> &a, pair<ll, ll> &b){
	if(a.second==b.second){
		return a.first<b.first;
	}
	return a.second<b.second;
}
ll dist(pair<ll, ll> &a, pair<ll, ll> &b){
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
bool comp(pair<ll, ll> &a, pair<ll, ll> &b){
	ll c=CCW(v[0], a, b);
	if(c==0){
		return dist(v[0], a)<dist(v[0], b);
	}
	return c>0;
}//custom sorting : 우선순위인 것이 먼저가 되도록 sorting
double line_dist(pair<ll, ll> x, pair<pair<ll, ll>, pair<ll, ll>> line){
	double m1=line.first.second-line.second.second;
	double m2=line.first.first-line.second.first;
	double m3=line.first.second*line.second.first-line.first.first*line.second.second; 
	double upper=abs(m1*x.first-m2*x.second-m3);
	double nupper=sqrt(m1*m1+m2*m2);
	return upper/nupper;
}
bool allin(ll j, pair<pair<ll, ll>, pair<ll ,ll>> line){
	double distance=line_dist(ans[j], line);
	for(int i=0;i<ans.size();i++){
		if(i==j) continue;
		else if(line.first==ans[i] or line.second==ans[i]) continue;
		if(line_dist(ans[i], line)>=distance+0.01) return false;
	}
	return true;
}
int main(){
	while(true){
		cnt++;
		while(!ans.empty()) ans.pop_back();
		ll n;
		cin >> n;
		if(n==0) break;
		for(int i=0;i<n;i++){
			cin >> v[i].first >> v[i].second;
		}
		sort(v, v+n, ycomp);
		sort(v+1, v+n, comp);
		stack<pair<ll, ll>> s;
		s.push(v[0]);
		s.push(v[1]);
		for(int i=2;i<n;i++){
			pair<ll, ll> a, b;
			while(s.size()>=2){
				b=s.top();
				s.pop();
				a=s.top();
				if(CCW(a, b, v[i])>0){
					s.push(b);
					break;
				}
			}
			s.push(v[i]);
		}
		vector<pair<pair<ll, ll>, pair<ll, ll>>> l;
		ans.resize(s.size());
		while(!s.empty()){
			ans[s.size()-1]=s.top();
			s.pop();
		}
		for(int i=0;i<ans.size()-1;i++){
			l.push_back({ans[i], ans[i+1]});
		}
		l.push_back({ans[ans.size()-1], ans[0]});
		double minn=1e9+7;
		for(int i=0;i<l.size();i++){
			for(int j=0;j<ans.size();j++){
				if(l[i].first==ans[j] or l[i].second==ans[j]) continue;
				if(allin(j, l[i])){
					double d=line_dist(ans[j], l[i]);
					if(minn>d) minn=d;
				}
			}
		}
		printf("Case %d: %.2f\n", cnt, ceil(minn*100)/100);
	}
}

 

 

자, 여기서 의문이 들 수 있는 부분이 있다.

왜 비교 부분에 0.01이 뜬금포로 들어가 있죠?

 

double 자료형 사이에서는 쉽게 비교 연산자를 사용해선 안 된다. 부동 소수점 오차에 의해 잘못된 결과를 반환할 수도 있기 때문이다. 그러나, 이런 오차는 적어도 소수점 아래 둘째자리보다 밑에서 발생한다. 그리고, 문제의 조건에서, 모든 점은 정수점이므로, 점과 직선 사이의 거리는 적어도 모두 1보다 크거나 같다. 그러므로, 차이가 난다면 1이상이므로, 두 거리가 같은 경우를 보정하기 위해, distance에 0.01로써 이를 보정해 준 것이다(같다면, 둘 사이 차가 0.01이하이므로 false를 return 하지 않는다). 이런 식으로 야매(?)로 오차를 보정할 수 있다.

1트

오랜만에 추억의 convex hull을 하니까 기분이 좋기는 개뿔이지 기하알고리즘 다 뒤졌으면 좋겠다. 이상

 

 

+여담

https://namu.wiki/w/%EB%8D%94%EC%8A%A4%ED%8A%B8%EC%8A%88%ED%8A%B8

더스트슈트

진짜 있는 거였네?