首页 > ACM题库 > HDU-杭电 > hdu 2581 Bomb the Bridge-计算几何-[解题报告]C++
2014
02-10

hdu 2581 Bomb the Bridge-计算几何-[解题报告]C++

Bomb the Bridge

问题描述 :

You want to destroy a bridge with bombs .The lower-left corner of the bridge is at (0,0) and upper-right corner is at ( w , l ). There are already b bombs exploded , the i-th bombcreated a hole of radius ri centering at (xi , yi) .You want to throw exactly one more bomb so that the bridge is split into two connected parts( though the two parts can share a finite number of points),so that no one can go through the bridge from y=0 to y=l .You task is to find the minimal radius of the last bomb to split the bridge , assuming that the last bomb can explode precisely at the position you want (possibly at non-integer
coordinates).Note that you are only allowed to use bombs with integer radius .That is ,even if a bomb with radius 1.01 is sufficient , you have to use a bomb with radius 2, since you only have bombs with integer radius.

输入:

The first line contains t (1<= t <=10), the number of test cases followed . Each test case begins with three integers w , l, b (1<= w , l<=100 , 0<= b <= 10). Each of the following b lines contains three integers integers xi, yi , ri (0<= x <=w, 0<= y <=l, 0< r <=100). The bridge is guaranteed to be connected before the last bomb.

输出:

The first line contains t (1<= t <=10), the number of test cases followed . Each test case begins with three integers w , l, b (1<= w , l<=100 , 0<= b <= 10). Each of the following b lines contains three integers integers xi, yi , ri (0<= x <=w, 0<= y <=l, 0< r <=100). The bridge is guaranteed to be connected before the last bomb.

样例输入:

3
100 100 2
15 50 20
90 50 30 
100 100 1
50 50 40
100 100 1
10 50 10

样例输出:

13 
50 
40

昨天练习赛中的一道计算几何题目,开始相当然的以为在这100*100的范围内枚举每个点的情况就可以,结果悲剧的WA了,之后考虑2个圆的圆心距,但是考虑问题的时候由于没能考虑全面,这个时候这题已经花了差不多2个小时。

其实现在想起来,计算几何的题目关键在于前期思考题目的时候一定要全面的考虑问题,如果某些情况没能想好而去写代码,这样不仅自己不能短时间内解决问题,而且耽误队友的时间。

好了,还是来说下这道题目吧,题意是,在一个w*l的矩阵内,由于炸弹可以炸掉b个圆形的范围,现在要你求出最后一个这样的炸弹可以使得从y = 0 —-y = l不存在一条路。

说下自己的解法,其实还是很简单的,首先读入的时候就预处理,分成lec和ric以及exc,其中exc表示没有和左右边界有交点的圆,然后就是在exc中查找那些可能是通过其他圆和边界相连的情况,然后这里可以使用dfs,不过感觉还是2重循环写起来思路清晰点,今天WA了10次都是悲剧的在ceil函数的精度上,其实做计算几何题目,这也是第三次WA在精度问题上面了, 以后一定得注意。

 

代码冗长,以后写得注意!~

#include<iostream>
#include<cstdio>
#include<cmath>
#include<memory.h>
#include<algorithm>

#define esp 1e-8
#define inf 1<<30
#define size 20
using namespace std;
struct circle
{
    double x,y,r;
};
circle lec[size];
circle ric[size];
circle exc[size];

int cntl;
int cntr;
int cnte;

bool vis[size];

int main ()
{
    int t;
    int w,l,b;
    int x,y,r;
    scanf(“%d”,&t);
    while(t–)
    {
        scanf(“%d%d%d”,&w,&l,&b);
        cntl = 0;
        cntr = 0;
        cnte = 0;
        for(int i = 0;i < b;++i)
        {
            scanf(“%d%d%d”,&x,&y,&r);
            if(x – r <= 0)
                lec[cntl].x = x,lec[cntl].y = y,lec[cntl++].r = r;
            else if(x + r >= w)
                ric[cntr].x = x,ric[cntr].y = y,ric[cntr++].r = r;
            else
                exc[cnte].x = x,exc[cnte].y = y,exc[cnte++].r = r;
        }
        memset(vis,0,sizeof(vis));
        for(int i = 0;i < cnte;++i)
        {
            for(int j = 0;j < cnte;++j)
            {
                if(vis[j])
                    continue;
                int k;
                for(k = 0;k < cntl;++k)
                    if(sqrt((exc[j].x – lec[k].x)*(exc[j].x – lec[k].x)
                       + (exc[j].y – lec[k].y)*(exc[j].y – lec[k].y)) <= (exc[j].r + lec[k].r))
                           break;
                if(k < cntl)
                {
                    flag = true;
                    vis[j] = 1;
                    lec[cntl].x = exc[j].x;
                    lec[cntl].y = exc[j].y;
                    lec[cntl++].r = exc[j].r;
                }
            }
        }
        for(int i = 0;i < cnte;++i)
        {
            for(int j = 0;j < cnte;++j)
            {
                if(vis[j])
                    continue;
                int k;
                for(k = 0;k < cntr;++k)
                    if(sqrt((exc[j].x – ric[k].x)*(exc[j].x – ric[k].x)
                             + (exc[j].y – ric[k].y)*(exc[j].y – ric[k].y)) <= exc[j].r + ric[k].r)
                            break;
                if( k < cntr)
                {
                    flag = true;
                    vis[j] = 1;
                    ric[cntr].x = exc[j].x;
                    ric[cntr].y = exc[j].y;
                    ric[cntr++].r = exc[j].r;
                }
            }
        }
        double minvalue = inf;
        if(cntl > 0 && cntr > 0)
        {
            for(int i = 0;i < cntl;++i)
            {
                for(int j = 0;j < cntr;++j)
                {
                    double dis = sqrt((lec[i].x – ric[j].x) * (lec[i].x – ric[j].x)
                                       + (lec[i].y – ric[j].y) * (lec[i].y – ric[j].y)) – lec[i].r – ric[j].r;
                    if(dis < minvalue)
                        minvalue = dis;
                }
            }
        }
        if (cntl == 0 && cntr == 0)
        {
            int res;
            minvalue = w;
            minvalue /= 2;
            if((minvalue – int(minvalue)) < esp) res = int(minvalue);
            else res = int(minvalue) + 1;
            printf(“%d\n”,res);
            continue;
        }
        int maxvalue = 0;
        for(int i = 0;i < cntl;++i)
        {
            if(maxvalue < lec[i].x + lec[i].r)
                maxvalue = lec[i].x + lec[i].r;
        }
        for(int i = 0;i < cntr;++i)
        {
            if(maxvalue < w – ric[i].x + ric[i].r)
                maxvalue = w – ric[i].x + ric[i].r;
        }
        double ans = w – maxvalue;
        if(ans > minvalue)
            ans = minvalue;
        int res;
        ans /= 2;
        if((ans – int(ans)) < esp) res = int(ans);
        else res = int(ans) + 1;
        printf(“%d\n”,res);

    }
    return 0;
}

解题转自:http://blog.163.com/archer_nzy/blog/static/133382582201149102748659/


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。