题目链接：
http://acm.timus.ru/problem.aspx?space=1&num=1215
坑爹的题，让我交了17次才过。。。。这。。
几个关键点。（判断点在“凸”多边形内，果断用叉积判断而非“角和”判断吧。我不知道ural怎么做到的，我把eps开到了1都能把我的“角和”判断卡掉，太nb了。）
1.叉积判断点在多边形内或上
如果旋转叉积过程中出现“正”以及“负”号情况发生，则点在“凸”多边形外。前提，点按顺/逆时针给出。
2.点到线段的距离
根据点积判断点与线段两端点组成的三角形的两个底角（相对于用于判断的点而言）是否均非钝角。
若有一个钝角，则点到线段的距离为点到两端点距离中的小者；若无，则为垂足距离。
（自己写的几何模板不要偷懒。。能用向量绝不解析。。。不然卡精度卡死你。。还有，有标准做法的，千万不要用偷懒做法水过去，不然以后会后悔的）
附代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#define sqr(x) ((x) * (x))
using namespace std;
#define maxn 105
const double eps = 1e-6;
const double pi = acos(-1.0);
int comp(double x)
{
if(fabs(x) < eps)
return 0;
else if(x < -eps)
return -1;
else
return 1;
}
struct point
{
int x,y;
point(){}
point(int a,int b):x(a),y(b){}
point operator -(const point &p)
{
return point(x - p.x,y - p.y);
}
int operator *(const point &p)
{
return x * p.x + y * p.y;
}
int operator ^(const point &p)
{
return x * p.y - y * p.x;
}
int norm2()
{
return sqr(x) + sqr(y);
}
}p[maxn],o;
int multi(point a,point b,point o)
{
return (a - o) ^ (b - o);
}
int scalar(point a,point b,point o)
{
return (a - o) * (b - o);
}
int n;
int main()
{
int a,b;
scanf("%d %d",&a,&b);
o = point(a,b);
scanf("%d",&n);
for(int i = 0;i < n;i++)
{
scanf("%d %d",&a,&b);
p[i] = point(a,b);
}
bool pos = false,neg = false;
for(int i = 0;i < n;i++)
{
int a = i,b = (i + 1) % n;
int flag = multi(p[a],p[b],o);
if(flag > 0 && !pos)
pos = true;
if(flag < 0 && !neg)
neg = true;
}
if(!(neg && pos))
{
printf("%.3lf\n",0.0);
return 0;
}
double r = 1e10;
for(int i = 0;i < n;i++)
{
int a = i,b = (i + 1) % n;
double lab = sqrt((double)(p[a] - p[b]).norm2()),lbo = sqrt((double)(o - p[b]).norm2()),lao = sqrt((double)(o - p[a]).norm2());
int sbao = scalar(p[b],o,p[a]),sabo = scalar(p[a],o,p[b]);
double bao = acos((double) sbao / (lab * lao)),abo = acos((double)sabo / ( lab * lbo));
if(comp(bao - pi / 2.0) <= 0 && comp(abo - pi / 2.0) <= 0)
r = min(r,fabs((double)multi(p[a],p[b],o)) / lab);
else
r = min(r,min(lbo,lao));
}
printf("%.3lf\n",r * 2.0);
}
Down