[cpp]
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位小數。
二分的算法是很好出的：每次把陸地向外推出一個距離，然後判斷所有的航線是否被覆蓋，這樣做就等價於題目中所描述的孤地點了。
但是，我苦逼地寫了 3 遍才 A 。。。。計算幾何的代碼量真是動辄一百多行啊。。。
先隨便亂寫了一個，結果寫的稀亂而且各種 WA 。。。
然後，我發現多邊形的頂點向外推將形成一個圓弧。一開始，我試圖直接將多邊形用圓弧和線段描述出來，但是發現這樣有一個嚴重的問題：多邊形是任意多邊形而不是凸多邊形。這樣一來如果有角大於平角則必然會將兩條邊重疊地推出，然後圓弧也就亂了，於是直接求交便是不可能的了。
之後我干脆把多邊形剖分成原多邊形和多個矩形和多個扇形。然後由於是完全覆蓋的，所以扇形當作圓處理即可。結果不但好寫而且一下就 A 了。。。
錯點：
其一，當一條直線穿過多邊形的一個頂點時，如果用兩條邊去交或者不交，都會導致出現奇數個點。。。所以需要用點交或者判重。。。（我是用點交的。。。）
其二，當判斷一個點是否在一個線段上，且如不在則按情況分別返回兩端點。這裡各種平行於坐標軸的線段簡直虐翻我了。。。
Code :
[cpp]
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define eps 0.000000001
#define oo 999999999999.
struct point {double x, y;};
struct seg {point x, y;};
struct line {point f; double c;};
int sig(double a) {return a < - eps ? - 1 : a > eps;}
double len(point a) {return sqrt(a.x * a.x + a.y * a.y);}
double operator *(point a, point b) {return a.x * b.y - a.y * b.x;}
double operator %(point a, point b) {return a.x * b.x + a.y * b.y;}
point operator +(point a, point b) {return (point) {a.x + b.x, a.y + b.y};}
point operator -(point a, point b) {return (point) {a.x - b.x, a.y - b.y};}
point operator *(line a, line b)
{
double c = a.f * b.f;
return (point) {(b.f.y * a.c - a.f.y * b.c) / c,
(a.f.x * b.c - b.f.x * a.c) / c};
}
point make_point(point a, double dist)
{
double x = a.x * a.x;
double y = a.y * a.y, z = x + y;
return (point) {sqrt(x * dist * dist / z) * sig(a.x),
sqrt(y * dist * dist / z) * sig(a.y)};
}
line make_line(seg a)
{
point f = (point) {a.y.y - a.x.y, a.x.x - a.y.x};
return (line) {f, f.x * a.x.x + f.y * a.x.y};
}
point select(seg a, point b)
{
if (sig(a.x.x - a.y.x))
{
if ((a.x.x - b.x) * (a.y.x - b.x) < eps) return b;
if (a.x.x > a.y.x) swap(a.x, a.y);
return b.x < a.x.x ? a.x : a.y;
}
else
{
if ((a.x.y - b.y) * (a.y.y - b.y) < eps) return b;
if (a.x.y > a.y.y) swap(a.x, a.y);
return b.y < a.x.y ? a.x : a.y;
}
}
point operator *(seg a, line b)
{
point p = make_line(a) * b;
if (sig(a.x.x - a.y.x) && (a.x.x - p.x) * (a.y.x - p.x) > - eps) return (point) {oo};
if (sig(a.x.y - a.y.y) && (a.x.y - p.y) * (a.y.y - p.y) > - eps) return (point) {oo};
return p;
}
point cross_circle(line a, seg b)
{
line l = make_line(b);
line r = (line) {(point) {l.f.y, - l.f.x}, a.f.x * l.f.y - a.f.y * l.f.x};
point p = l * r, q;
double dist = len(p - a.f), A, B;
if (dist - a.c > - eps) return (point) {oo};
dist = sqrt(a.c * a.c - dist * dist);
q = make_point(b.x - b.y, dist);
A = len(select(b, p + q) - b.x), B = len(select(b, p - q) - b.x);
return A < B ? (point) {A, B} : (point) {B, A};
}
void cross_poly(int k, point poly[], seg b, int & tot, point u[])
{
int i, j; double a[31];
seg s; point p; line l = make_line(b); j = 0;
for (i = 1; i <= k; ++ i)
{
s = (seg) {poly[i - 1], poly[i]}, p = s * l;
if (p.x != oo) a[++ j] = len(select(b, p) - b.x);
if (! sig((b.x - poly[i]) * (b.y - poly[i])))
a[++ j] = len(select(b, poly[i]) - b.x);
}
sort(a + 1, a + j + 1);
for (i = 1; i <= j; i += 2)
u[++ tot] = (point) {a[i], a[i + 1]};
}
int C, n;
int num[35], total[35];
point fli[35];
point lan[35][35], cover[35][1000];
bool cmp(point A, point B) {return A.x < B.x;}
bool okay(double dist)
{
int i, j, k, tot; double le;
point p; point cov[1000], poly[6]; seg s;
for (i = 2; i <= n; ++ i)
{
tot = total[i], memcpy(cov, cover[i], sizeof cover[i]);
for (j = 1; j <= C; ++ j)
{
s = (seg) {fli[i - 1], fli[i]};
for (k = 1; k <= num[j]; ++ k)
{
p = cross_circle((line) {lan[j][k], dist}, s);
if (p.x != oo) cov[++ tot] = p;
p = lan[j][k] - lan[j][k - 1];
p = make_point((point) {p.y, - p.x}, dist);
poly[1] = lan[j][k - 1], poly[2] = lan[j][k - 1] + p;
poly[3] = lan[j][k] + p, poly[0] = poly[4] = lan[j][k];
cross_poly(4, poly, s, tot, cov);
}
}
sort(cov + 1, cov + tot + 1, cmp);
p = cov[1], le = 0;
for (j = 2; j <= tot; ++ j)
if (cov[j].x > p.y) le += p.y - p.x, p = cov[j];
else if (cov[j].y > p.y) p.y = cov[j].y;
le += p.y - p.x;
if (len(s.y - s.x) - le > eps) return 0;
}
return 1;
}
int main()
{
freopen("1020.in", "r", stdin);
freopen("1020.out", "w", stdout);
int i, j; double l, r, s;
scanf("%d%d", & C, & n);
for (i = 1; i <= n; ++ i)
scanf("%lf%lf", & fli[i].x, & fli[i].y);
for (i = 1; i <= C; ++ i)
{
scanf("%d", num + i);
for (j = 1; j <= num[i]; ++ j)
scanf("%lf%lf", & lan[i][j].x, & lan[i][j].y);
s = lan[i][num[i]] * lan[i][1];
for (j = 2; j <= num[i]; ++ j)
s += lan[i][j - 1] * lan[i][j];
if (s < - eps)
for (j = 1; j << 1 <= num[i]; ++ j)
swap(lan[i][j], lan[i][num[i] - j + 1]);
lan[i][0] = lan[i][num[i]];
for (j = 2; j <= n; ++ j)
cross_poly(num[i], lan[i], (seg) {fli[j - 1], fli[j]}, total[j], cover[j]);
}
for (l = 0, r = 10000; r - l > 0.001; )
okay(s = (l + r) / 2) ? r = s : l = s;
printf("%.2lf", s);
return 0;
}
