/** 这一做用了差不多5个小时,又是一道手机提交AC 的题 此题主要思想:建图和检查连通性,这里用并查集实现 题意:穿越1000*1000的正方形田野,要求从田野左边界进入从右边界出来,田野里面有 n条蛇,每条蛇都有自己的以(x,y)为圆心r为半径的领地,如果他一旦跃入蛇的领地内(注意是 < r), 将会被咬,问他能否安全穿越这片田野。 解析:初看一筹莫展,无从下手,躺下想了几分钟后有了大概思路,接着实现,调试 1、首先放开其它条件只考虑是否能顺利通过,怎样才能顺利通过 2、脑子里面是否有条从上边界到下边界的曲线,如果这条曲线是封闭的,他就不能过来 3、怎样构造这条曲线?连接圆心。 4、连接哪两个圆圆心?能够相交的圆圆心。 5、把上边界下边界看成两个点标号为0和n+1,如有圆与其相交则连接圆心与其连接。 6、现在已经大概能呈现一幅图的画面了。图中的点为边界和圆心构成 例:输入数据 2 400 400 500 600 600 500 把两个圆心标号为1、2,根据上述条件可建立如下图 <0,1> <1,2> <2,3> 图中有 0,1,2,3 四个点 3条边 可以看到从边界0到3是联通的,所以他不能顺利通过 如下代码具体实现 */ #include <math.h> #include <stdio.h> #include <string.h> #define sqr(x) ((x)*(x)) #include <algorithm> using namespace std; const int M = 1005; struct point { double x, y, r; }p[M]; // 圆心的数据结构 struct lr { double u, d; int i; }l[M], r[M]; // 实现从边界最北边的点进入田野,暂且不要考虑 bool map[M][M]; // map[1][2] == true,则1、2两点存在边<1,2> int path[M]; // 并查集的数据结构和kruskal算法中的并查一样 /////////////////////////////////////////// // 并查集得函数,并查集只是实现这道题的工具, // 其实好多题不是专门考会不会用工具,而掌握 // 这些工具是做题必不可少的技能,剩下的工作 // 才是动脑子来 AC int find(int x) { if (x != path[x]) path[x] = find(path[x]); return path[x]; } // 这也是实现从最北边进入田野的函数,暂且不考虑 bool jud(lr tt[], double x, int n) { for (int i=0; i<n; i++) if (tt[i].u > x && tt[i].d < x) return false; return true; } int main() { int n; while (scanf("%d", &n)!=EOF) { memset(map, 0, sizeof (map)); int ll=0, rr=0; // 下面循环用于输入圆心坐标和建立与上下左右边界关系 for (int i=1; i<=n; i++) { scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].r); if (p[i].y+p[i].r > 1000) // 与上边界的关系 map[0][i] = map[i][0] = true; if (p[i].y-p[i].r < 0) // 与下边界的关系 map[n+1][i] = map[i][n+1] = true; // 判断是否能顺利通过只考虑与上下边界关系即可 // 下面建立左右边界是为了完成题目输出要求,先不必考虑 if (p[i].x-p[i].r < 0) { // 与左边界的关系 // l[ll].u, l[ll].d,l[0].i = i, 表示第ll个点, // 圆心为i,在左边界上相交区间的为(l[ll].d, l[ll].u) l[ll].u = p[i].y + sqrt(sqr(p[i].r)-sqr(p[i].x)); l[ll].d = p[i].y - sqrt(sqr(p[i].r)-sqr(p[i].x)); l[ll++].i = i; } if (p[i].x+p[i].r > 1000) { r[rr].u = p[i].y + sqrt(sqr(p[i].r)-sqr(1000-p[i].x)); r[rr].d = p[i].y - sqrt(sqr(p[i].r)-sqr(1000-p[i].x)); r[rr++].i = i; } } // 建立各个圆心之间的关系,上下边界与圆心关系在上面循环中已经建好 for (int i=1; i<n; i++) for (int j=i+1; j<=n; j++) { if (p[i].r+p[j].r > sqrt(sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y))) { map[i][j] = map[j][i] = true; } } // 到目前为止上面建图中除了不必考虑的部分,还是非常好理解的 // 下面是实现并查集的初始化 for (int i=0; i<=n+1; i++) path[i] = i; /////////////////////////////////////////////// // 经过下面的对每个有联系的点进行并查集处理后, // 如想判断两个点a,b是否属于一个集合只需 // if (find(a) == find(b)) // 则a,b在同一个集合,即a和b联通 /////////////////////////////////////////////// for (int i=0; i<=n; i++) for (int j=i+1; j<=n+1; j++) { if (map[i][j]) { int x = find(i); int y = find(j); if (x != y) path[y] = x; } } if (find(n+1) == find(0)) // 如果上边界和下边界在一个集合,则联通 printf("Bill will be bitten.\n"); ///////////////////////////////////////////////// // 实现上面只用了半个小时,下面的选取 // 最高点着实错了有7、8次,最后用最简单的思想实现了 // 但还是感觉非常冗余,反正是过了,实在不想再想了 //////////////////////////////////////////////// else { double lflag = -1, rflag = -1; // lflag 记录左边界可进入的最高点, rflag记录可从右边界出来的最高点 double lu=1000, ld=0, ru=1000, rd=0; // lu表示左边界可用区间的最高点,ld左边界可用区间的最低点 ///////////////////////////////////////////////////// // 下面的循环找出可用区间(ld, lu), 因为如果find(a)==find(0) // 圆a 又与左边界相交,相交部分到最高点1000,都是不可用的, for (int i=0; i<ll; i++) { if (find(l[i].i)==find(0) && l[i].d < lu) lu = l[i].d; if (find(l[i].i)==find(n+1) && l[i].u > ld) ld = l[i].u; } ///////////////////////////////////////////////////////// // 判断最高点 1000 是否可用,如果在圆和左边界相交区域则不可用 // 例如:l[ll].u == 1200 l[ll].d == 800, 1000位于(800,1200)区间 if (jud(l,1000,ll) && lu==1000) lflag = 1000; ///////////////////////////////////////////// // 最高点一定坐落在左边界的最高点或与圆的交点 // 所以判断交点是否在可用区间,判断交点是否可用,判断lflag 是否值得替换 for (int i=0; i<ll; i++) { if (l[i].u<=lu && l[i].u>=ld && jud(l,l[i].u,ll) && lflag < l[i].u) { lflag = l[i].u; } if (l[i].d<=lu && l[i].d>=ld && jud(l,l[i].d,ll) && lflag < l[i].d) { lflag = l[i].d; } } //下面是右边界处理如左边界 for (int i=0; i<rr; i++) { if (find(r[i].i)==find(0) && r[i].d < ru) ru = r[i].d; if (find(r[i].i)==find(n+1) && r[i].u > rd) rd = l[i].u; } if (jud(r,1000,rr) && ru==1000) rflag = 1000; for (int i=0; i<rr; i++) { if (r[i].u<=ru && r[i].u>=rd && jud(r,r[i].u,rr) && rflag < r[i].u) { rflag = r[i].u; } if (r[i].d<=ru && r[i].d>=rd && jud(r,r[i].d,rr) && rflag < r[i].d) { rflag = r[i].d; } } if (ll == 0) lflag = 1000; if (rr == 0) rflag = 1000; if (rflag<0 || lflag<0) printf("Bill will be bitten.\n"); else printf("Bill enters at (0.00, %.2lf) and leaves at (1000.00, %.2lf).\n", lflag, rflag); } } return 0; }