2013-02-15 15:12:48Morris
[UVA][SSSP] 10947 - Bear with me, again..
Problem E: Bear with me, again..
There are bears everywhere! In fact, look around, there might be one around you!
Okay, maybe not.
Here's the story:
Larry is trying to come up with some kind of escape plan from the island.. and then realizes that he's struck with nothing except for Ryan, some duct tape, and some cardboard. What are the odds? He knows how to (somewhat) build a raft of sorts from it! Unforunately for Larry, since his craftmenship isn't quite good, not to mention he really have no tools, he can only build a raft that lasts K straight days at sea, after of which if it can get to an island, it can be fixed up and reused. He notices that he and Ryan can row at a speed of M miles per day. Still, with some luck, and Ryan's GPS (which came with the super-iPod, you see), he is able to see islands from far far away. Somehow all the islands are perfectly circular... and he knows exactly where home is.. can he get there, hopping on islands along the way?
So doing some calculations, he realizes his fate..
Input
Everything will in miles.First line will contain the integers K and M, as defined above in the problem.
The second line of each input will contain three integers, space limited: x, y, r. x and y being the coordinates of the current island, the r being the radius of the island (somehow, all the islands are perfectly circular.)
Third line will contain three integers in the same format as above, will contain the location and radius of the island they want to get to.
Then there will be a single integer N which is followed by N lines, each in the format of x_i, y_i, and r_i, each representing an island coordinate and its radius in miles. N will be at most 100.
No islands will have overlaps, and all integers representing coordinates and radius will be less than 200.
Output
For each test case, outputLarry and Ryan will escape!if they can get back to their home island in some way, or
Larry and Ryan will be eaten to death.if they cannot get home.
Sample Input
1 1 0 0 1 0 3 1 0 1 1 0 0 1 0 5 1 0 1 1 0 0 1 0 6 1 1 0 3 1
Sample Output
Larry and Ryan will escape! Larry and Ryan will be eaten to death. Larry and Ryan will escape!
uHunt 說是 All pairs，但看懂題目就是 SSSP, Dijkstra 可做的。
簡單的說一天最長移動距離 K*M，他說了一次最多在海上航行 K 天，每天最多移動 M 距離。
之後把島之間算連線距離即可。
#include <stdio.h>
#include <math.h>
#define oo 1000000000
int main() {
double K, M;
double g[105][105];
while(scanf("%lf %lf", &K, &M) == 2) {
double mxDis = K*M, dis, tmp;
double x[105], y[105], r[105];
int n, i, j, k;
scanf("%lf %lf %lf", &x[0], &y[0], &r[0]);
scanf("%lf %lf %lf", &x[1], &y[1], &r[1]);
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lf %lf %lf", &x[i+2], &y[i+2], &r[i+2]);
n += 2;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
tmp = sqrt(pow(x[i]-x[j],2) + pow(y[i]-y[j],2));
if(tmp <= r[i]+r[j])
dis = 0;
else
dis = tmp - r[i]- r[j];
if(dis > mxDis) g[i][j] = oo;
else g[i][j] = dis;
}
}
for(k = 0; k < n; k++)
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(g[i][j] > g[i][k]+g[k][j])
g[i][j] = g[i][k]+g[k][j];
if(g[0][1] != oo)
puts("Larry and Ryan will escape!");
else
puts("Larry and Ryan will be eaten to death.");
}
return 0;
}