Description
在设计航线的时候，安全是一个很重要的问题。首先，最重要的是应采取一切措施确保飞行不会发生任何事故，但同时也需要做好最坏的打算，一旦事故发生，就要确保乘客有尽量高的生还几率。当飞机迫降到海上的时候，最近的陆地就是一个关键的因素。航线中最危险的地方就是距离最近的陆地最远的地方，我们称这种点为这条航线“孤地点”。孤地点到最近陆地的距离被称为“孤地距离”。作为航空公司的高级顾问，你接受的第一个任务就是尽量找出一条航线的孤地点，并计算这条航线的孤地距离。为了简化问题，我们认为地图是一个二维平面，陆地可以用多边形近似，飞行线路为一条折线。航线的起点和终点都在陆地上，但中间的转折点是可能在海上（如下图所示，方格标示出了孤地点）。 
Input
输入的第一行包括两个整数C和N（1≤C≤20，2≤N≤20），分别代表陆地的数目的航线的转折点的数目。接下来有N行，每行有两个整数x,y。(x,y)表示一个航线转折点的坐标，第一个转折点为航线的起点，最后一个转折点为航线的终点。接下来的输入将用来描述C块大陆。每块输入由一个正整数M开始（M≤30），M表示多边形的顶点个数，接下来的M行，每行会包含两个整数x,y，(x,y)表示多边形的一个顶点坐标，我们保证这些顶点以顺时针或逆时针给出了该多边形的闭包，不会出现某些边相交的情况。此外我们也保证输入数据中任何两块大陆不会相交。输入的所有坐标将保证在-10000到10000的范围之间。
Output
输出一个浮点数，表示航线的孤地距离，数据保留2位小数。
Sample Input
1 2
-9 -6
5 1
3
0 16
-16 -12
17 -6
-9 -6
5 1
3
0 16
-16 -12
17 -6
Sample Output
0.00
吐槽：不得不说这种计算几何题TTM恶心了，对着数据(70个点用geogebra一一手打)调了3天。功夫不负有心人，还是切掉了。感谢我们学校的大神犇莫涛学长的算法，不然像我这种蒟蒻恐怕一辈子都写不出二分答案的正解。
为了表示膜拜，我将我的做法口述一遍吧(其实就是莫涛学长在论文上写的那种迭代)，忽然间感觉自己和ydc比起来写得好丑。
- 先将所有不在多边形内部的线段加入队列中；
- 取出队首线段，找出与左端点最近的多边形上的点p1，右端点最近的多边形上的点p2。ans = max(ans,dis(p1,左端点),dis(p2,右端点))；
- 在线段上二分出一个点p，使得dis(p,p1) == dis(p,p2)；
- 若dis(p,p1) < ans，continue；否则，将线段二等分加入队列中；
- 重复2，3,4直到队列为空；
算法(减枝)就是这样。为什么这样是对的呢？我们证明一下：
我们现在要讨论的就是这个算法的正确性
现在我们有一条线段和对应的p1和p2，分别是左端点最近的点和右端点最近的点
有三种情况
然后我们发现线段上的点到自己最近点的距离不会超过max(dis(p1,p),dis(a,p1),(b,p2))（a，b分别为线段的左右端点）
所以我们的删除操作是对的，我们删除的都是不会更新答案的线段，就像ydc说的一样，这个就像是搜索剪枝
(注：上述证明转自:http://www.cnblogs.com/Randolph87/p/3642917.html)
最后再贴一份自己丑丑的代码：
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std; #define rhl 10001
#define esp (1e-4)
#define maxn (30)
#define maxc (30)
#define maxm (40)
int tot,n,c,have[maxc]; double ans; inline double equal(double a,double b) { return fabs(a-b) < esp; } inline bool dd(double a,double b) { if (equal(a,b)) return true; return a >= b; } //>= inline bool xd(double a,double b) { if (equal(a,b)) return true; return a <= b; } //<= struct NODE
{
double x,y;
friend inline bool operator == (NODE a,NODE b) { return equal(a.x,b.x)&&equal(a.y,b.y); }
friend inline bool operator < (NODE a,NODE b)
{
if (a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
inline NODE ra()
{
int xx,yy;
do xx = rand()%rhl,yy = rand()%rhl;
while (equal(1.0*xx,x)||equal(1.0*yy,y));
return (NODE) {1.0*xx,1.0*yy};
}
inline void read() { scanf("%lf %lf",&x,&y); }
}pol[maxc][maxm],bac[maxc*maxm];
struct LINE
{
double a,b,c;
friend inline bool operator ==(LINE l1,LINE l2) { return equal(l1.a*l2.c,l2.a*l1.c); }
inline LINE vert(NODE p) { return (LINE) {b,-a,a*p.y-b*p.x}; }
inline bool on(NODE p) { return equal(,a*p.x+b*p.y+c); }
};
struct SEG{
NODE a,b;
inline NODE MID() { return (NODE) {(a.x+b.x)/,(a.y + b.y)/}; }
inline bool exist() { return !(a == b); }
inline LINE extend() { return (LINE) {a.y-b.y,b.x-a.x,b.y*(a.x-b.x)-b.x*(a.y-b.y)}; }
inline bool on(NODE p)
{
if (p == a) return true;
if (p == b) return true;
return (dd(p.x,min(a.x,b.x))&xd(p.x,max(a.x,b.x)))&&(dd(p.y,min(a.y,b.y))&xd(p.y,max(a.y,b.y)));
}
}temp[maxn];
queue <SEG> team; inline bool para(LINE l1,LINE l2) { return equal(l1.a * l2.b,l1.b * l2.a); } inline double qua(double a) { return a * a; } inline double dis(NODE a,NODE b) { return sqrt(qua(a.x - b.x)+qua(a.y - b.y)); } inline NODE cp(LINE l1,LINE l2)
{
double a1 = l1.a,b1 = l1.b,c1 = l1.c;
double a2 = l2.a,b2 = l2.b,c2 = l2.c;
double ry = (c2*a1-c1*a2)/(b1*a2-b2*a1),rx = (c1*b2-c2*b1)/(b1*a2-b2*a1);
return (NODE) {rx,ry};
} inline void cross(SEG s,int now)
{
LINE l = s.extend(),l1; SEG t; NODE p; NODE tt[maxm];
int cnt = ;
for (int i = ;i <= have[now];++i)
{
t = (SEG) {pol[now][i],pol[now][i-]};
l1 = t.extend();
if (para(l,l1))
{
if (l == l1)
{
if (s.on(t.a)) tt[++cnt] = t.a;
if (s.on(t.b)) tt[++cnt] = t.b;
}
continue;
}
p = cp(l,l1);
if (t.on(p) && s.on(p))
tt[++cnt] = p;
}
sort(tt+,tt+cnt+);
for (int i = ;i <= cnt;++i) bac[++tot] = tt[i];
} inline NODE find(NODE p)
{
NODE ret,q; LINE l1,l2; SEG s; double best = 1e9,len;
for (int i = ;i <= c;++i)
for (int j = ;j <= have[i];++j)
{
s = (SEG) {pol[i][j],pol[i][j-]};
l1 = s.extend();
l2 = l1.vert(p);
q = cp(l1,l2);
if (s.on(q))
{
len = dis(p,q);
if (best > len) ret = q,best = len;
}
else
{
if (dis(p,s.a) < dis(p,s.b)) q = s.a;
else q = s.b;
len = dis(p,q);
if (best > len) ret = q,best = len;
}
}
return ret;
} inline bool in(NODE p)
{
NODE q = p.ra(); SEG s = (SEG) {p,q},t; LINE l = s.extend(),l1; int cnt;
for (int i = ;i <= c;++i)
{
cnt = ;
for (int j = ;j <= have[i];++j)
{
t = (SEG) {pol[i][j],pol[i][j-]};
if ((t.extend()).on(p)&&t.on(p)) return false;
l1 = t.extend();
if (para(l,l1)) continue;
q = cp(l,l1);
if (dd(q.x,p.x)&&t.on(q)) ++cnt;
}
if (cnt & ) return true;
}
return false;
} inline void init()
{
for (int i = ;i < n;++i)
{
tot = ;
if (!(temp[i].a < temp[i].b)) swap(temp[i].a,temp[i].b);
for (int j = ;j <= c;++j)
cross(temp[i],j);
if (!in(temp[i].a)) bac[++tot] = temp[i].a;
if (!in(temp[i].b)) bac[++tot] = temp[i].b;
sort(bac+,bac+tot+);
for (int j = ;j < tot;j++)
if (!in((SEG){bac[j],bac[j+]}.MID()))
team.push((SEG){bac[j],bac[j+]});
}
} inline void work()
{
SEG now; NODE mid,p1,p2,l,r; double ret;
while (!team.empty())
{
now = team.front(); team.pop();
if (!now.exist()) continue;
p1 = find(now.a); p2 = find(now.b);
l = now.a,r = now.b;
while (!(l == r))
{
mid = ((SEG){l,r}).MID();
if (dis(p1,mid) > dis(p2,mid)) r = mid;
else l = mid;
}
ret = dis(r,p1);
ans = max(max(dis(now.a,p1),dis(now.b,p2)),ans);
if (ret-esp < ans) continue;
mid = now.MID();
team.push((SEG){now.a,mid}),team.push((SEG){mid,now.b});
}
} int main()
{
srand();
ans = ;
scanf("%d %d ",&c,&n);
NODE p1,p2; p1.read();
for (int i = ;i <= n;++i)
{
p2.read(); temp[i-] = (SEG) {p1,p2};
p1 = p2;
}
for (int i = ;i <= c;++i)
{
scanf("%d ",have+i);
for (int j = ;j <= have[i];++j) pol[i][j].read();
pol[i][] = pol[i][have[i]];
}
init();
work();
printf("%.2lf\n",ans);
fclose(stdin); fclose(stdout);
return ;
}