timus 1215. Exactness of Projectile Hit URAL 解题报告
题目描述真是无语，大概是一个导弹有一个落点，给定坐标； 然后有一个目标区域，问导弹的最小轰炸直径是多少时才能满足目标区域内至少有一个点被攻击到！
其实就是求点到凸包的最短距离的2倍！
首先，判断点是不是在凸包内部，是的话输出0.000
不是的话，判断点到每一条线段的距离即可，选出最短的距离就是半径，然后输出直径就好！ 注意G++输出的时候只能用printf（“%.3f”） 而不能用lf输出…… 有懂的留言讨论下……
有两个地方需要注意：
1.判断点是否在凸包内部，假如在凸包内部的话，连续三个点，p1,p2,p3 那么p-p1,p-p2,p-p3旋转顺序是相同的； 反之叉积<0 就不在内部， 碰到共线的情况下不用管它，肯定还有不共线的情况，如果该点不在内部的话，至于为什么会成立，我暂且不知道6
2.判断点到线段的距离，有两种方法这里
1）找到一点t是的pt与p1p2垂直，然后看看pp1与pp2是不是pt的同侧，在同侧的话是钝角三角形，那么垂足一定不再线段p1p2上；
如果在的话利用等面积法就好了，注意叉积的集合意义，其大小等于面积或者体积（2维或3维的情况）
2）或者直接利用勾股定理判断是不是钝角三角形，其目的是判断垂足是不是在线段上，然后就利用等面积法……
文中判断大小的时候貌似不太严格，double判断大小的情况请移步，小媛在努力的CSDN博客……
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define N 100000
#define EPS 1e-7
struct Point
{
double x,y;
int id;
}pot[N],po;
int n;
double cross(Point p,Point p1,Point p2)
{///向量pp1 * pp2
double x1=p1.x-p.x,y1=p1.y-p.y;
double x2=p2.x-p.x,y2=p2.y-p.y;
return x1*y2-x2*y1;
}
bool cover()
{///如果点在凸包内部的话，那么书序连接它与各个顶点，相邻的点旋转顺序一定是一样的，注意如果有点在共线的情况，先不用管他
///后来还出出现特殊情况的
pot[n]=pot[0];
pot[n+1]=pot[1];
pot[n+2]=pot[2];
for(int i=0;i<=n;++i)
{
if(cross(po,pot[i],pot[i+1])*cross(po,pot[i+1],pot[i+2])<0 )
return false;
}
return true;///点在凸包内部
}
double dis2(Point p1,Point p2)
{
return sqrt( pow(p1.x-p2.x,2.0) +pow(p1.y-p2.y,2.0) );
}
double disptoseg(Point p,Point p1,Point p2)
{///返回点到线段的距离
if(dis2(p1,p2)==0)return dis2(p,p1);
Point t=po;///注意这里的构建,这里是构建一个点t是的pt与p1p2垂直
t.y+=p1.x-p2.x;
t.x+=p2.y-p1.y;
if( cross(t,p,p1)*cross(t,p,p2)>=0 )
{///如果是钝角
return min( dis2( p,p1),dis2(p,p2) );
}
///如果是锐角三角形，那么就用等面积法求解
return fabs( cross(p,p1,p2) )/ dis2(p1,p2) ;
}
double disptosegment(point p1, point p2, point p3)
{///点到线段距，p1为点，p2-p3为线段 这是另外一种构建方法
///如果点和点a或者点b重合
double a = dis(p1, p2);
double b = dis(p1, p3);
if(a < eps || b < eps) return 0;
///如果a,b重合，线段是一个点的情况
double c = dis(p2, p3);
if(c < eps) return a;
///垂足不在线段上，即三角形是钝角三角形
if(a*a >= b*b+c*c) return b;
if(b*b >= a*a+c*c) return a;
///一般情况下就是利用等面积法
double l = (a+b+c)/2.0;
double s = sqrt(l*(l-a)*(l-b)*(l-c));
return 2.0*s/c;
}
int main()
{
while(cin>>po.x>>po.y>>n)
{
for(int i=0;i<n;++i)
{
cin>>pot[i].x>>pot[i].y;
}
if(cover())
{
cout<<0.000<<endl;
}else
{
pot[n]=pot[0];
double ans=1e30;
double tmp;
for(int i=0;i<n;++i)
{
tmp=disptoseg(po,pot[i],pot[i+1]);
if(tmp<ans)ans=tmp;
}
printf("%.3f\n",ans*2+EPS);
}
}
return 0;
}