4225 쓰레기 슈트 https://www.acmicpc.net/problem/4225
다각형이 주어진다.
이 다각형을 어느 공간으로 넣을때 부딪치지 않고 통과할 수 있는 최소 너비를 구하는 문제다.
이 문제는 CCW를 이용해서 $O(N^3)$만에 풀 수 있다.
먼저 어느 한점과 또 다른 한점을 있는 직선을 생각해보자.
이 직선을 기준으로 Y축과 평행하게 도형을 놓는다면 다음과 같은 형태가 될것이다.
이 상태에서 도형의 너비는 직선을 기준으로 왼쪽에 점과 오른쪽에 있는 점의 직선과의 최대거리의 합이 되겠다.
여기서 직선의 왼쪽, 오른쪽을 판별하는게 CCW(Counter Clock Wise)가 되겠다.
사실 CCW개념을 모르고 풀었는데 한점과 직선과의 거리는 다음과 같이 나타낼 수 있다.
$|ax+by+c|/\sqrt{a^2+b^2}$
여기서 분자부분만 보면 이 값이 양수면 직선기준으로 반시계방향, 음수면 시계방향이라고한다.
처음에 잡은 두 점으로 $a, b$를 구하고 나머지 한점에 $x, y$를 대입해주면 그 값을 구할 수 있다.
최댓값들을 구해서 $\sqrt{a^2+b^2}$으로 나눠주고 그값들중 최솟값을 구하면 된다.
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point{
int x,y;
Point(){}
Point(int xx,int yy):x(xx),y(yy){}
Point operator-(Point const &other){
return Point(x-other.x,y-other.y);
}
};
int N;
Point p[101];
int main(){
int cnt = 1;
while(scanf("%d",&N), N != 0){
for(int n=0;n<N;n++) scanf("%d%d",&p[n].x,&p[n].y);
double ans = 1e13;
for(int n=0;n<N;n++){
for(int m=n+1;m<N;m++){
int a,b,c;
a = p[m].y - p[n].y;
b = p[n].x - p[m].x;
c = p[n].y*(p[m].x-p[n].x) - p[n].x*(p[m].y-p[n].y);
double Min = 1e10, Max = -1e10;
for(int k=0;k<N;k++){
double d = a*p[k].x + b*p[k].y + c;
if(d < 0) Min = min(Min, d);
else if(d > 0) Max = max(Max, d);
}
double get = 0.0;
if(Min < 0) get -= Min;
if(Max > 0) get += Max;
get /= sqrt(a*a+b*b);
ans = min(ans, get);
}
}
printf("Case %d: %.2lf\n",cnt++,ans + 0.005);
}
}
| cs |
댓글 없음:
댓글 쓰기