[计算几何][SHOI2008]安全的航线flight(二)

2014-11-24 08:53:02 · 作者: · 浏览: 4
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;
}