这套题比较。。。有意思。。。
Assemble据说是简单题
March of the Penguins你看相传每个ice floes是有跳的次数限制的是吧。。。用经典的拆点流量限制法，每个ice floes拆成i和i'，i到i'的流量上限为跳的次数，然后如果能从i跳到j连一条i'到j的边(流量无穷大)。。。点数好像有点多。。。不要客气～，dinic很快的～
Containers推一下式子，在实数意义下可以求最值是吧。然后现在限制整数。。。上下浮动一下吧。。。
| Youth Hostel Dorm
相当麻烦的状态压缩dp，还么写。。。
Escape from Enemy Territory
二分 + bfs应该可以，或者排个序 + 并查集
Flight Safety
比较麻烦的计算几何题。大体的想法是二分答案 + judge。得知了答案r以后我们可以把整个多边形往外膨胀r个单位然后判断是否整条路线都在里面。具体实现的时候我们把整个图形拆成原来的多边形，一堆矩形（每天边对应一个矩形）和一堆圆（每个点对应一个圆），每一部分求一下航线有哪些部分在里面，最后判断是否整条航线都被包含了。。。
  CODE
1 // Northwestern Europe 2007, Flight Safety
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <cmath>
8#include <vector>
9#include <algorithm>
10
11using namespace std;
12
13const double eps = 1e-8;
14struct Point  {
15 double x, y;
16  Point() {}
17 Point(double _x, double _y) : x(_x), y(_y) {}
18 bool operator<(const Point &p) const {
19 if (fabs(x - p.x) > eps) return x < p.x;
20 else return y < p.y;
21 }
22 double length_to(const Point &p) const {
23 return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
24 }
25 }oo(223456789.0, 897654321.0);
26
27double point_segment(const Point &p0, const Point &p1, const Point &p2);
28void adjust_len(double len, double &x, double &y);
29bool inside_segment(const Point &p0, const Point &p1, const Point &p2);
30bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d, Point &p);
31bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d);
32double cross(const Point &p0, const Point &p1, const Point &p2);
33
34struct Shape {
35 virtual bool inside(const Point &x) = 0;
36 virtual void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) = 0;
37};
38struct Circle : Shape {
39 Point o;
40 double r;
41 bool inside(const Point &x) {
42 return o.length_to(x) < r + eps;
43 }
44 void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) {
45 if (inside(p0) && inside(p1)) {
46 lst.push_back(make_pair(p0, p1));
47 return;
48 }
49
50 double dist = point_segment(o, p0, p1);
51 if (dist + eps > r) return;
52
53 double dx = -(p1.y - p0.y), dy = (p1.x - p0.x);
54 adjust_len(dist, dx, dy);
55 Point mid(o.x + dx, o.y + dy);
56
57 if (fabs(cross(p0, p1, mid)) > eps)
58 mid = Point(o.x - dx, o.y - dy);
59
60 dx = p1.x - p0.x; dy = p1.y - p0.y;
61 adjust_len(sqrt(r * r - dist * dist), dx, dy);
62 Point t1(mid.x + dx, mid.y + dy), t2(mid.x - dx, mid.y - dy);
63
64 bool in1 = inside_segment(t1, p0, p1), in2 = inside_segment(t2, p0, p1);
65 if (in1 && in2) lst.push_back(make_pair(t1, t2));
66 else if (in1 && (!in2)) lst.push_back(make_pair(p0, t1));
67 else if (in2 && (!in1)) lst.push_back(make_pair(t2, p1));
68 }
69};
70struct Polygon : Shape {
71 int n;
72 Point p[40];
73 bool inside(const Point &x) {
74 int cnt = 0;
75 for (int i = 0; i < n; ++i)
76 if (seg_cross(x, oo, p[i], p[i + 1])) ++cnt;
77 return cnt % 2;
78 }
79 void append_segment(const Point &p0, const Point &p1, vector<pair<Point, Point> > &lst) {
80 vector<Point> x;
81 x.push_back(p0); x.push_back(p1);
82 for (int i = 0; i < n; ++i) {
83 Point tmp;
84 if (seg_cross(p0, p1, p[i], p[i + 1], tmp)) {
85 x.push_back(tmp);
86 }
87 }
88
89 sort(x.begin(), x.end());
90 for (int i = 0; i + 1 < x.size(); ++i) {
91 Point mid((x[i].x + x[i + 1].x) / 2.0, (x[i].y + x[i + 1].y) / 2.0);
92 if (inside(mid))
93 lst.push_back(make_pair(x[i], x[i + 1]));
94 }
95
96 }
97};
98
99Polygon poly[30];
100Circle cir[30][30];
101Polygon rect[30][30];
102Point route[30];
103int c, n;
104
105void init();
106void work();
107bool judge_valid(double r);
108bool xy_cmp(double x0, double x1, double x2);
109int sgn(double x);
110
111int main() {
112 int t;
113 cin >> t;
114 for (; t > 0; --t) {
115 init();
116 work();
117 }
118 return 0;
119}
120
121void init() {
122 cin >> c >> n;
123 for (int i = 0; i < n; ++i)
124 cin >> route[i].x >> route[i].y;
125
126 for (int i = 0; i < c; ++i) {
127 cin >> poly[i].n;
128 for (int j = 0; j < poly[i].n; ++j)
129 cin >> poly[i].p[j].x >> poly[i].p[j].y;
130 poly[i].p[poly[i].n] = poly[i].p[0];
131 }
132}
133
134void work() {
135 const double Accurate = 1e-4;
136 double h = 0.0, t = 30000.0, mid = (h + t) / 2.0;
137 for (; h + Accurate < t; mid = (h + t) / 2.0) {
138 if (judge_valid(mid)) t = mid;
139 else h = mid;
140 }
141
142 printf("%.15lf\n", mid);
143}
144
145
146double point_segment(const Point &p0, const Point &p1, const Point &p2) {
147 return cross(p0, p1, p2) / p1.length_to(p2);
148}
149
150void adjust_len(double len, double &x, double &y) {
151 double ratio = len / sqrt(x * x + y * y);
152 x *= ratio; y *= ratio;
153}
154
155bool inside_segment(const Point &p0, const Point &p1, const Point &p2) {
156 if (fabs(p2.x - p1.x) > fabs(p2.y - p1.y))
157 return xy_cmp(p0.x, p1.x, p2.x);
158 else
159 return xy_cmp(p0.y, p1.y, p2.y);
160}
161
162bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d, Point &p) {
163 double s1 = cross(a, b, c), s2 = cross(a, b, d), s3 = cross(c, d, a), s4 = cross(c, d, b);
164 int d1 = sgn(s1), d2 = sgn(s2), d3 = sgn(s3), d4 = sgn(s4);
165
166 if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) {
167 p.x = (c.x * s2 - d.x * s1) / (s2 - s1);
168 p.y = (c.y * s2 - d.y * s1) / (s2 - s1);
169 return true;
170 }
171
172 return false;
173}
174
175bool seg_cross(const Point &a, const Point &b, const Point &c, const Point &d) {
176 double s1 = cross(a, b, c), s2 = cross(a, b, d), s3 = cross(c, d, a), s4 = cross(c, d, b);
177 int d1 = sgn(s1), d2 = sgn(s2), d3 = sgn(s3), d4 = sgn(s4);
178
179 return ((d1 ^ d2) == -2 && (d3 ^ d4) == -2);
180}
181 |