BZOJ 1020 安全的航线

1020: [SHOI2008]安全的航线flight

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 1462  Solved: 503
[Submit][Status][Discuss]

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

Sample Output

0.00

HINT

 

Source

思路:用个队列存储所有要处理的线段。对每截线段分别求出端点s距多边形的最近点a和t的最近点b,用sa和tb更新答案,在s、t之间找到p使得pa = pb,易知st上所有点对答案的贡献都不超过pa,由此在此处剪枝。
如剪不掉,将两截子线段都加入队列中。
代码:
  1 #include <iostream>
  2 #include <fstream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <string>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <set>
 14 #include <map>
 15 #include <list>
 16 #include <iomanip>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <bitset>
 20 #include <ctime>
 21 
 22 using namespace std;
 23 
 24 #define pau system("pause")
 25 #define ll long long
 26 #define pii pair<int, int>
 27 #define pb push_back
 28 #define pli pair<ll, int>
 29 #define pil pair<int, ll>
 30 #define clr(a, x) memset(a, x, sizeof(a))
 31 
 32 const double pi = acos(-1.0);
 33 const int INF = 0x3f3f3f3f;
 34 const int MOD = 1e9 + 7;
 35 const double EPS = 1e-9;
 36 
 37 /*
 38 #include <ext/pb_ds/assoc_container.hpp>
 39 #include <ext/pb_ds/tree_policy.hpp>
 40 using namespace __gnu_pbds;
 41 #define TREE tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update>
 42 TREE T;
 43 */
 44 
 45 int sgn(double x) {return x < -EPS ? -1 : (x < EPS ? 0 : 1);}
 46 struct Point {
 47     double x, y;
 48     Point () {}
 49     Point (double x, double y) : x(x), y(y) {}
 50     Point operator + (const Point &p) const {return Point(x + p.x, y + p.y);}
 51     Point operator - (const Point &p) const {return Point(x - p.x, y - p.y);}
 52     Point operator * (const double &k) const {return Point(x * k, y * k);}
 53     Point operator / (const double &k) const {return Point(x / k, y / k);}
 54     double operator ^ (const Point &p) const {return x * p.y - y * p.x;}
 55     double operator | (const Point &p) const {return x * p.x + y * p.y;}
 56     bool operator < (const Point &p) const {return sgn(x - p.x) ? x < p.x : y < p.y;}
 57     double len2() {return x * x + y * y;}
 58     double len() {return sqrt(len2());}
 59     void input() {scanf("%lf%lf", &x, &y);}
 60     void output() {printf("%.6f %.6f
", x, y);}
 61 } p[205];
 62 #define pdp pair<double, Point>
 63 struct Line {
 64     Point s, e;
 65     Line () {}
 66     Line (Point s, Point e) : s(s), e(e) {}
 67     Point operator & (const Line &l) const {
 68         double k1 = (l.s - s) ^ (l.e - s);
 69         double k2 = (l.e - e) ^ (l.s - e);
 70         return (s * k2 + e * k1) / (k1 + k2);
 71     }
 72     bool operator | (const Point &p) const {// now on line but not seg
 73         double x1 = min(s.x, e.x), x2 = max(s.x, e.x);
 74         double y1 = min(s.y, e.y), y2 = max(s.y, e.y);
 75         return 0 <= sgn(p.x - x1) && 0 <= sgn(x2 - p.x) && 
 76                 0 <= sgn(p.y - y1) && 0 <= sgn(y2 - p.y);
 77     }
 78     pdp dis(Point p) {
 79         if (0 < ((p - s) | (e - s)) && ((p - s) | (e - s)) < (e - s).len2()) {
 80                return pdp(fabs((p - s) ^ (e - s)) / (e - s).len(), s + (e - s) * ((p - s) | (e - s)) / (e - s).len2());
 81         } else {
 82             double ds = (p - s).len(), de = (p - e).len();
 83             if (ds < de) {
 84                 return pdp(ds, s);
 85             } else {
 86                 return pdp(de, e);
 87             }
 88         }
 89     }        
 90     double len() {
 91         return (e - s).len();
 92     }
 93 } l[205];
 94 struct State {
 95     Point p; int f;
 96     bool operator < (const State &s) const {
 97         return p < s.p;
 98     }
 99 };
100 struct Pol {
101     int n; Point p[35]; Line l[35];
102     Point gpoint() {
103         double S = 0; Point res = Point(0, 0);
104         for (int i = 1; i <= n; ++i) {
105             double s = p[i] ^ p[i % n + 1];
106             res = res + (p[i] + p[i % n + 1]) / 3 * s;
107             S += s;
108         }
109         return res / S;
110     }
111     bool hasp(Point p) {
112         Line key = Line(p, p + Point(INF, 0));
113         int f = 0;
114         for (int i = 1; i <= n; ++i) {
115             if (!sgn(l[i].e.y - l[i].s.y)) continue;
116             int f1 = sgn(l[i].s.y - p.y);
117             int f2 = sgn(l[i].e.y - p.y);
118             if (f1 == f2) continue;
119             Point tp = key & l[i];
120             if (sgn(tp.x - p.x) == -1) continue;
121             f += (f1 < f2 ? -1 : 1) * (!!f1 + !!f2);
122         }
123         return f;
124     }
125     pdp dis(Point p) {
126         if (hasp(p)) return pdp(0, p);
127         pdp res = pdp(1e18, Point(0, 0));
128         for (int i = 1; i <= n; ++i) {
129             pdp tt = l[i].dis(p);
130             res = min(res, tt);
131         }
132         return res;
133     }
134     void input() {
135         scanf("%d", &n);
136         for (int i = 1; i <= n; ++i) {
137             p[i].input();
138         }
139         for (int i = 1; i <= n; ++i) {
140             l[i] = Line(p[i], p[i % n + 1]);
141         }
142     }
143 } pol[22];
144 int c, n;
145 double ans;
146 void solve() {
147     queue<Line> que;
148     for (int i = 1; i < n; ++i) {
149         que.push(l[i]);
150     }
151     while (que.size()) {
152         Line l = que.front(); que.pop();
153         Point s = l.s, e = l.e;
154         if ((s - e).len() < 1e-3) continue;
155         double ds = INF, de = INF;
156         Point a, b;
157         for (int i = 1; i <= c; ++i) {
158             pdp td = pol[i].dis(s);
159             if (td.first < ds) {
160                 ds = td.first;
161                 a = td.second;
162             }
163             td = pol[i].dis(e);
164             if (td.first < de) {
165                 de = td.first;
166                 b = td.second;
167             }
168         }
169         ans = max(ans, max(ds, de));
170         double sta = 0, en = 1, mi;
171         Point tp;
172         while (sta <= en - EPS) {
173             mi = (sta + en) * 0.5;
174             tp = s * mi + e * (1 - mi);
175             double d1 = (tp - a).len(), d2 = (tp - b).len();
176             if (d1 < d2) {
177                 en = mi;
178             } else {
179                 sta = mi;
180             }
181         }
182         if ((tp - a).len() < ans) continue;
183         que.push(Line(s, tp));
184         que.push(Line(e, tp));
185     }
186 }
187 int main() {
188     scanf("%d%d", &c, &n);
189     for (int i = 1; i <= n; ++i) {
190         p[i].input();
191     }
192     for (int i = 1; i < n; ++i) {
193         l[i] = Line(p[i], p[i + 1]);
194     }
195     for (int i = 1; i <= c; ++i) {
196         pol[i].input();
197     }        
198     solve();
199     printf("%.2f
", ans);
200     return 0;
201 }
View Code
原文地址:https://www.cnblogs.com/BIGTOM/p/10570094.html