问题 H: Planar map
时间限制: 1 Sec 内存限制: 128 MB
提交: 24 解决: 22
[提交][状态][讨论版]
题目描述
Tigher has work for a long time in a famous company.One day she is given a planar map(look at
the following) and a point.The planar map can be regarded as a polygon.The planar map has n
positions,which are the n vertexes in the polygon.
Actually the point replace the position of a supermarket.The supermarket has a range of its
effect,which show as a circle.The company wants to know the maximum radius of the
circle.Unfortunately,Tigher decides to see movie with her BF this evening.So she give the project
to the ipqhjjybj(so poor!).However,ipqhjjybj want to have dinner with his new friends(do you
remember the “hengheng eat noodles” last time),so he throw the project to you.Can you solve it?
输入
An interger CASE ,which means the total case num.
For every case, the first line is an interger means n.(1<=n<=6)
Then will be n lines (x , y) which indicates the n points' position.
The n+2 line will be the coordinate of the supermarket,and we promise that this point must be in the internal of the planar map.
And this n points will form n lines , which is (n1, n2) (n2 , n3) (n3 ,n4) (n4, n5)...(nn,n1)
输出
It will give just an real number . (Preserve 3 decimal places)
样例输入
4
4
0 0
2 0
2 2
0 2
1 1
1
1 1
1 1
6
0 0
2 0
3 1
2 2
1 1
0 2
1 0.5
3
0 0
0 1
1 0
0.5 0.5
样例输出
1.000
0.000
0.500
0.000
提示
对所有线段取点到线段距离最小值
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct pnt{
double x,y;
pnt(){x=y=0;}
pnt(double x,double y){this->x=x;this->y=y;}
};
pnt pt[100];
int n;
double caldis(pnt a,pnt b){return sqrt((a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x));}
double calc(pnt o,pnt a,pnt b){
if(a.y==b.y){
if(o.x<=max(a.x,b.x)&&o.x>=min(a.x,b.x))return fabs(o.y-a.y);
else return min(caldis(o,a),caldis(o,b));
}
else if(a.x==b.x){
if(o.y<=max(a.y,b.y)&&o.y>=min(a.y,b.y))return fabs(o.x-a.x);
else return min(caldis(o,a),caldis(o,b));
}
else{
double k=(b.y-a.y)/(b.x-a.x);
double tx=o.y-a.y+k*a.x+o.x/k;
tx/=(k+1/k);
double ty=k*(tx-a.x)+a.y;
if(tx<=max(a.x,b.x)&&tx>=min(a.x,b.x)&&ty<=max(a.y,b.y)&&ty>=min(a.y,b.y)){
return caldis(o,pnt(tx,ty));
}
else return min(caldis(o,a),caldis(o,b));
}
}
int main(){
int T;
scanf("%d",&T);
for(int ti=0;ti<T;ti++){
scanf("%d",&n);
pnt o;
for(int i=0;i<n;i++){
scanf("%lf%lf",&pt[i].x,&pt[i].y);
}
scanf("%lf%lf",&o.x,&o.y);
double ans=1e19;
for(int i=0;i<n;i++){
ans=min(ans,calc(o,pt[i],pt[(i+1)%n]));
}
printf("%.3f\n",ans);
}
return 0;
}