2014
02-10

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

#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;
}

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;