「POJ2588」Snakes
Description
Buffalo Bill wishes to cross a 1000×1000 square field. A number of snakes are on the field at various positions, and each snake can strike a particular distance in any direction. Can Bill make the trip without being bitten?
Input
Assume that the southwest corner of the field is at (0,0) and the northwest corner at (0,1000). The input consists of a line containing n <= 1000, the number of snakes. A line follows for each snake, containing three real numbers: the (x,y) location of the snake and its strike distance. The snake will bite anything that passes closer than this distance from its location.
Output
Bill must enter the field somewhere between the southwest and northwest corner and must leave somewhere between the southeast and northeast corners.
If Bill can complete the trip, give coordinates at which he may enter and leave the field. If Bill may enter and leave at several places, give the most northerly. If there is no such pair of positions, print “Bill will be bitten.”
Sample Input
|
1 2 3 4 |
3 500 500 499 0 0 999 1000 1000 200 |
Sample Output
|
1 |
Bill enters at (0.00, 1000.00) and leaves at (1000.00, 800.00). |
题解
复制一份嘿嘿嘿
这样处理以后如果有从左到右的路径，当且仅当不存在S到T通路！只要深搜或者广搜即可！但是题目还要我们求出左右的坐标，只需确定纵坐标即可，而且纵坐标要最大！所以我们考虑与S连通的每一个点，如果该点代表的圆与左边界有交点，那么如果从这个交点上面走一定走不过去，所以我们更新左边的纵坐标到这个交点处，对所有的圆都这样处理，即可确定左边纵坐标，右边的同理可求！而且这一步可以在求连通的时候随便求出，我们只需从S出发，一直搜即可！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int n;double maxl=1000,maxr=1000; int ft[1005]; double ld[1005],rd[1005]; bool mark[1005],l[1005],r[1005],u[1005],d[1005]; struct data{double x,y,r;}a[1005]; int find(int x){return x==ft[x]?x:ft[x]=find(ft[x]);} void un(int x,int y) { int p=find(x),q=find(y); if(p!=q)ft[p]=q; } double sqr(double x){return x*x;} double dis(data a,data b) {return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));} void build() { for(int i=1;i<=n;i++) { if(a[i].y+a[i].r>1000)u[i]=1; if(a[i].r>a[i].y)d[i]=1; if(a[i].x<a[i].r) {l[i]=1;ld[i]=a[i].y-sqrt(sqr(a[i].r)-sqr(a[i].x));} if(a[i].x+a[i].r>1000) {r[i]=1;rd[i]=a[i].y-sqrt(sqr(a[i].r)-sqr(1000-a[i].x));} for(int j=i+1;j<=n;j++) if(dis(a[i],a[j])<a[i].r+a[j].r) un(i,j); } } bool work() { for(int i=1;i<=n;i++) if(!mark[i]&&u[i]) for(int j=1;j<=n;j++) if(find(i)==find(j)) { mark[j]=1; if(d[j]){printf("Bill will be bitten.");return 0;} if(l[j])maxl=min(maxl,ld[j]); if(r[j])maxr=min(maxr,rd[j]); } return 1; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)ft[i]=i; for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r); build(); if(work()) printf("Bill enters at (0.00, %.2lf) and leaves at (1000.00, %.2lf).",maxl,maxr); return 0; } |
Subscribe
计数器 9855402
OI 课件=>
OI 课件=>