HDU 4063 Aircraft(計算ジオメトリ)(The 36 th ACM/IPCC Asia Regional Fuzhou Site-Online Contest)
69242 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4063
Description
You are playing a flying game.
In the game, player controls an aircraft in a 2D-space.
The mission is to drive the craft from starting point to terminal point.
The craft needs wireless signal to move.
A number of devices are placed in the 2D-space, spreading signal.
For a device Di, it has a signal radius -- Ri.
When the distance between the craft and Di is shorter or equal to Ri, it(the craft) gets Di's wireless signal.
Now you need to tell me the shortest path from starting point to terminal point.
Input
The first line of the input file is a single integer T.
The rest of the test file contains T blocks.
Each block starts with an integer n, followed by n devices given as (xi, yi, Ri).
(xi, yi) is position of Di, and Ri is the radius of its signal range.
The first point is the starting point.
The last point is the terminal point.
T <= 25;
2 <= n <= 20 for most cases;
20 < n <= 25 for several cases, completely random generated.
-1000 <= xi, yi <= 1000 , 1 <= ri <= 1000.
All are integers.
Output
For each case, Output "No such path."if the craft can't get to the terminal point.
Otherwise, output a float number, correct the result to 4 decimal places.(as shown in the sample output)
テーマ大意&問題解:http://blog.csdn.net/zxy_snow/article/details/6849550
PS:首位共点の時にずっとNo such pathを出力していたのに気づかずに半日調整しましたが…
次は幾何学を計算する方法で、なぜかG++はずっとTLE(まさか私が書き間違えたの?)ということで、大量の関数演算を加えて最適化されなかったのかも・・・
ついでにテンプレートを貼ります
コード(C++750 MS):
View Code
次は幾何学を解析する方法の一部を用いて、上よりも速く・・・
コード(G++437 MS):
View Code
Description
You are playing a flying game.
In the game, player controls an aircraft in a 2D-space.
The mission is to drive the craft from starting point to terminal point.
The craft needs wireless signal to move.
A number of devices are placed in the 2D-space, spreading signal.
For a device Di, it has a signal radius -- Ri.
When the distance between the craft and Di is shorter or equal to Ri, it(the craft) gets Di's wireless signal.
Now you need to tell me the shortest path from starting point to terminal point.
Input
The first line of the input file is a single integer T.
The rest of the test file contains T blocks.
Each block starts with an integer n, followed by n devices given as (xi, yi, Ri).
(xi, yi) is position of Di, and Ri is the radius of its signal range.
The first point is the starting point.
The last point is the terminal point.
T <= 25;
2 <= n <= 20 for most cases;
20 < n <= 25 for several cases, completely random generated.
-1000 <= xi, yi <= 1000 , 1 <= ri <= 1000.
All are integers.
Output
For each case, Output "No such path."if the craft can't get to the terminal point.
Otherwise, output a float number, correct the result to 4 decimal places.(as shown in the sample output)
テーマ大意&問題解:http://blog.csdn.net/zxy_snow/article/details/6849550
PS:首位共点の時にずっとNo such pathを出力していたのに気づかずに半日調整しましたが…
次は幾何学を計算する方法で、なぜかG++はずっとTLE(まさか私が書き間違えたの?)ということで、大量の関数演算を加えて最適化されなかったのかも・・・
ついでにテンプレートを貼ります
コード(C++750 MS):
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <cmath>
6 using namespace std;
7 typedef long long LL;
8
9 const int MAXN = 22;
10 const int MAXV = MAXN * MAXN * 2;
11 const int MAXE = MAXV * MAXV;
12 const double EPS = 1e-6;
13 const double INF = 1e100;
14
15 inline double sqr(double x) {
16 return x * x;
17 }
18
19 inline int sgn(double x) {
20 return (x > EPS) - (x < -EPS);
21 }
22
23 struct Point {
24 double x, y;
25 Point() {}
26 Point(double x, double y): x(x), y(y) {}
27 void read() {
28 scanf("%lf%lf", &x, &y);
29 }
30 bool operator < (const Point &rhs) const {
31 if(sgn(x - rhs.x) != 0) return x < rhs.x;
32 return sgn(y - rhs.y) < 0;
33 }
34 bool operator == (const Point &rhs) const {
35 return sgn(x - rhs.x) == 0 && sgn(y - rhs.y) == 0;
36 }
37 Point operator + (const Point &rhs) const {
38 return Point(x + rhs.x, y + rhs.y);
39 }
40 Point operator - (const Point &rhs) const {
41 return Point(x - rhs.x, y - rhs.y);
42 }
43 double operator * (const Point &rhs) const {
44 return x * rhs.x + y * rhs.y;
45 }
46 Point operator * (double d) const {
47 return Point(x * d, y * d);
48 }
49 Point operator / (double d) const {
50 return Point(x / d, y / d);
51 }
52 Point rotate() const {
53 return Point(-y, x);
54 }
55 double length() const {
56 return sqrt(*this * *this);
57 }
58 };
59
60 double dist(const Point &a, const Point &b) {
61 return (a - b).length();
62 }
63
64 double cross(const Point &a, const Point &b) {
65 return a.x * b.y - a.y * b.x;
66 }
67
68 double cross(const Point &o, const Point &a, const Point &b) {
69 return cross(a - o, b - o);
70 }
71
72 double Point_to_Line(const Point &p, const Point &st, const Point &ed) {
73 return fabs(cross(p, st, ed)) / dist(st, ed);
74 }
75
76 Point intersection(const Point &u1, const Point &u2, const Point &v1, const Point &v2) {
77 double t = cross(u1 - v1, v1 - v2) / cross(u1 - u2, v1 - v2);
78 return u1 + (u2 - u1) * t;
79 }
80
81 struct Circle {
82 Point c;
83 double r;
84 Circle() {}
85 Circle(Point c, double r): c(c), r(r) {}
86 void read() {
87 c.read();
88 scanf("%lf", &r);
89 }
90 bool contain(const Circle &rhs) const {
91 return sgn(dist(c, rhs.c) + rhs.r - r) <= 0;
92 }
93 bool contain(const Point &p) const {
94 return sgn(dist(c, p) - r) <= 0;
95 }
96 bool intersect(const Circle &rhs) const {
97 return sgn(dist(c, rhs.c) - r - rhs.r) < 0;
98 }
99 bool tangency(const Circle &rhs) const {
100 return sgn(dist(c, rhs.c) - r - rhs.r) == 0;
101 }
102 };
103
104 int intersection(const Circle &cir, const Point &st, const Point &ed, Point &p1, Point &p2) {
105 if(sgn(Point_to_Line(cir.c, st, ed) - cir.r) > 0) return 0;
106 Point p = cir.c + (ed - st).rotate();
107 p = intersection(p, cir.c, st, ed);
108 double t = sqrt(sqr(cir.r) - sqr(dist(p, cir.c))) / dist(st, ed);
109 p1 = p + (ed - st) * t;
110 p2 = p - (ed - st) * t;
111 return 2 - (p1 == p2);
112 }
113
114 int intersection(const Circle &c1, const Circle &c2, Point &p1, Point &p2) {
115 if(c1.contain(c2) || c2.contain(c1)) return 0;
116 if(!c1.intersect(c2) && !c1.tangency(c2)) return 0;
117 double t = 0.5 * (1 + (sqr(c1.r) - sqr(c2.r)) / sqr(dist(c1.c, c2.c)));
118 Point u = c1.c + (c2.c - c1.c) * t, v = u + (c1.c - c2.c).rotate();
119 return intersection(c1, u, v, p1, p2);
120 }
121
122 struct Graph {
123 int head[MAXV], ecnt;
124 int to[MAXE], next[MAXE];
125 double cost[MAXE];
126 int n, st, ed;
127
128 void init() {
129 memset(head, -1, sizeof(head));
130 ecnt = 0;
131 }
132
133 void add_edge(int u, int v, double c) {
134 to[ecnt] = v; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;
135 to[ecnt] = u; cost[ecnt] = c; next[ecnt] = head[v]; head[v] = ecnt++;
136 }
137
138 double dis[MAXV];
139 bool vis[MAXV];
140
141 double dijksrta(int st, int ed, int n) {
142 for(int i = 0; i < n; ++i) dis[i] = INF;
143 dis[st] = 0;
144 memset(vis, 0, sizeof(vis));
145 while(true) {
146 int u = -1; double d = INF;
147 for(int i = 0; i < n; ++i) if(!vis[i])
148 if(dis[i] < d) d = dis[i], u = i;
149 if(d == INF) break;
150 vis[u] = true;
151 for(int p = head[u]; ~p; p = next[p]) {
152 int &v = to[p];
153 if(!vis[v]) dis[v] = min(dis[v], dis[u] + cost[p]);
154 }
155 }
156 return dis[ed];
157 }
158 } G;
159
160 Circle cir[MAXN];
161 int T, n;
162
163 Point list[MAXV];
164
165 bool havePath(Point st, Point ed) {
166 if(ed < st) swap(st, ed);
167 if(st == ed) return true;
168 Point p1, p2;
169 int pcnt = 0;
170 list[pcnt++] = st;
171 list[pcnt++] = ed;
172 for(int i = 0; i < n; ++i) {
173 int c = intersection(cir[i], st, ed, p1, p2);
174 if(c >= 1) list[pcnt++] = p1;
175 if(c >= 2) list[pcnt++] = p2;
176 }
177 sort(list, list + pcnt);
178 for(int i = 0; i < pcnt; ++i) {
179 if(list[i] < st || list[i] == st) continue;
180 bool flag = false;
181 for(int j = 0; j < n && !flag; ++j)
182 if(cir[j].contain(list[i]) && cir[j].contain(list[i - 1])) flag = true;
183 if(!flag) return false;
184 if(list[i] == ed) break;
185 }
186 return true;
187 }
188
189 Point p[MAXV];
190 int cnt;
191
192 double solve() {
193 Point p1, p2;
194 cnt = 0;
195 p[cnt++] = cir[0].c; p[cnt++] = cir[n - 1].c;
196 for(int i = 0; i < n; ++i) {
197 for(int j = i + 1; j < n; ++j) {
198 int c = intersection(cir[i], cir[j], p1, p2);
199 if(c >= 1) p[cnt++] = p1;
200 if(c >= 2) p[cnt++] = p2;
201 }
202 }
203 G.init();
204 for(int i = 0; i < cnt; ++i) {
205 for(int j = i + 1; j < cnt; ++j)
206 if(havePath(p[i], p[j])) G.add_edge(i, j, dist(p[i], p[j]));
207 }
208 return G.dijksrta(0, 1, cnt);
209 }
210
211 int main() {
212 scanf("%d", &T);
213 for(int kase = 1; kase <= T; ++kase) {
214 scanf("%d", &n);
215 for(int i = 0; i < n; ++i) cir[i].read();
216 double res = solve();
217 if(res == INF) printf("Case %d: No such path.
", kase);
218 else printf("Case %d: %.4f
", kase, res);
219 }
220 }View Code
次は幾何学を解析する方法の一部を用いて、上よりも速く・・・
コード(G++437 MS):
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <cmath>
6 #include <numeric>
7 using namespace std;
8 typedef long long LL;
9
10 const int MAXN = 44;
11 const int MAXV = MAXN * MAXN * 2;
12 const int MAXE = MAXV * MAXV;
13 const double EPS = 1e-12;
14 const double INF = 1e100;
15
16 inline double sqr(double x) {
17 return x * x;
18 }
19
20 inline int sgn(double x) {
21 return (x > EPS) - (x < -EPS);
22 }
23
24 struct Point {
25 double x, y;
26 Point() {}
27 Point(double x, double y): x(x), y(y) {}
28 void read() {
29 scanf("%lf%lf", &x, &y);
30 }
31 bool operator < (const Point &rhs) const {
32 if(sgn(x - rhs.x) != 0) return x < rhs.x;
33 return sgn(y - rhs.y) < 0;
34 }
35 bool operator == (const Point &rhs) const {
36 return sgn(x - rhs.x) == 0 && sgn(y - rhs.y) == 0;
37 }
38 Point operator + (const Point &rhs) const {
39 return Point(x + rhs.x, y + rhs.y);
40 }
41 Point operator - (const Point &rhs) const {
42 return Point(x - rhs.x, y - rhs.y);
43 }
44 double operator * (const Point &rhs) const {
45 return x * rhs.x + y * rhs.y;
46 }
47 Point operator * (double d) const {
48 return Point(x * d, y * d);
49 }
50 Point operator / (double d) const {
51 return Point(x / d, y / d);
52 }
53 Point rotate() const {
54 return Point(-y, x);
55 }
56 double length() const {
57 return sqrt(*this * *this);
58 }
59 };
60
61 double dist(const Point &a, const Point &b) {
62 return (a - b).length();
63 }
64
65 double cosIncludeAngle(const Point &a, const Point &b, const Point &o) {
66 Point p1 = a - o, p2 = b - o;
67 return (p1 * p2) / (p1.length() * p2.length());
68 }
69
70 struct Circle {
71 Point c;
72 double r;
73 Circle() {}
74 Circle(Point c, double r): c(c), r(r) {}
75 void read() {
76 c.read();
77 scanf("%lf", &r);
78 }
79 bool contain(const Circle &rhs) const {
80 return sgn(dist(c, rhs.c) + rhs.r - r) <= 0;
81 }
82 bool contain(const Point &p) const {
83 return sgn(dist(c, p) - r) <= 0;
84 }
85 bool intersect(const Circle &rhs) const {
86 return sgn(dist(c, rhs.c) - r - rhs.r) < 0;
87 }
88 bool tangency(const Circle &rhs) const {
89 return sgn(dist(c, rhs.c) - r - rhs.r) == 0;
90 }
91 };
92
93 int intersection(const Point &st, const Point &ed, const Circle &cir, Point &p1, Point &p2) {
94 double angle = cosIncludeAngle(ed, cir.c, st);
95 if(isnan(angle)) {
96 Point v = (ed - st) / dist(st, ed);
97 p1 = cir.c + v * cir.r;
98 p2 = cir.c - v * cir.r;
99 return 1 + (cir.r > 0);
100 }
101 double B = dist(cir.c, st);
102 double a = 1, b = -2 * B * angle, c = sqr(B) - sqr(cir.r);
103 double delta = sqr(b) - 4 * a * c;
104 if(sgn(delta) < 0) return 0;
105 if(sgn(delta) == 0) delta = 0;
106 double x1 = (-b - sqrt(delta)) / (2 * a), x2 = (-b + sqrt(delta)) / (2 * a);
107 Point v = (ed - st) / dist(ed, st);
108 p1 = st + v * x1;
109 p2 = st + v * x2;
110 return 1 + sgn(delta);
111 }
112
113 int intersection(const Circle &c1, const Circle &c2, Point &p1, Point &p2) {
114 if(c1.contain(c2) || c2.contain(c1)) return 0;
115 if(!c1.intersect(c2) && !c1.tangency(c2)) return 0;
116 double d = dist(c1.c, c2.c);
117 double d1 = (sqr(c2.r) + sqr(d) - sqr(c1.r)) / 2 / d;
118 double d2 = sqrt(sqr(c2.r) - sqr(d1));
119 Point v1 = c2.c + (c1.c - c2.c) / d * d1;
120 Point v2 = (c1.c - c2.c).rotate() / d;
121 p1 = v1 + v2 * d2;
122 p2 = v1 - v2 * d2;
123 return 2 - (p1 == p2);
124 }
125
126 struct Graph {
127 int head[MAXV], ecnt;
128 int to[MAXE], next[MAXE];
129 double cost[MAXE];
130 int n, st, ed;
131
132 void init() {
133 memset(head, -1, sizeof(head));
134 ecnt = 0;
135 }
136
137 void add_edge(int u, int v, double c) {
138 to[ecnt] = v; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;
139 to[ecnt] = u; cost[ecnt] = c; next[ecnt] = head[v]; head[v] = ecnt++;
140 }
141
142 double dis[MAXV];
143 bool vis[MAXV];
144
145 double dijksrta(int st, int ed, int n) {
146 for(int i = 0; i < n; ++i) dis[i] = INF;
147 dis[st] = 0;
148 memset(vis, 0, sizeof(vis));
149 while(true) {
150 int u = -1; double d = INF;
151 for(int i = 0; i < n; ++i) if(!vis[i])
152 if(dis[i] < d) d = dis[i], u = i;
153 if(d == INF) break;
154 vis[u] = true;
155 for(int p = head[u]; ~p; p = next[p]) {
156 int &v = to[p];
157 if(!vis[v]) dis[v] = min(dis[v], dis[u] + cost[p]);
158 }
159 }
160 return dis[ed];
161 }
162 } G;
163
164 Circle cir[MAXN];
165 int T, n;
166
167 Point list[MAXV];
168
169 bool havePath(Point st, Point ed) {
170 if(ed < st) swap(st, ed);
171 if(st == ed) return true;
172 Point p1, p2;
173 int pcnt = 0;
174 list[pcnt++] = st;
175 list[pcnt++] = ed;
176 for(int i = 0; i < n; ++i) {
177 int c = intersection(st, ed, cir[i], p1, p2);
178 if(c >= 1) list[pcnt++] = p1;
179 if(c >= 2) list[pcnt++] = p2;
180 }
181 sort(list, list + pcnt);
182 for(int i = 0; i < pcnt; ++i) {
183 if(list[i] < st || list[i] == st) continue;
184 bool flag = false;
185 //Point x = (list[i] + list[i - 1]) / 2;
186 for(int j = 0; j < n && !flag; ++j)
187 if(cir[j].contain(list[i]) && cir[j].contain(list[i - 1])) flag = true;
188 if(!flag) return false;
189 if(list[i] == ed) break;
190 }
191 return true;
192 }
193
194 Point p[MAXV];
195 int cnt;
196
197 double solve() {
198 Point p1, p2;
199 cnt = 0;
200 p[cnt++] = cir[0].c; p[cnt++] = cir[n - 1].c;
201 for(int i = 0; i < n; ++i) {
202 for(int j = i + 1; j < n; ++j) {
203 int c = intersection(cir[i], cir[j], p1, p2);
204 if(c >= 1) p[cnt++] = p1;
205 if(c >= 2) p[cnt++] = p2;
206 }
207 }
208 G.init();
209 for(int i = 0; i < cnt; ++i) {
210 for(int j = i + 1; j < cnt; ++j)
211 if(havePath(p[i], p[j])) G.add_edge(i, j, dist(p[i], p[j]));
212 }
213 return G.dijksrta(0, 1, cnt);
214 }
215
216 int main() {
217 scanf("%d", &T);
218 for(int kase = 1; kase <= T; ++kase) {
219 scanf("%d", &n);
220 for(int i = 0; i < n; ++i) cir[i].read();
221 double res = solve();
222 if(res == INF) printf("Case %d: No such path.
", kase);
223 else printf("Case %d: %.4f
", kase, res);
224 }
225 }View Code