题目
题目描述
一家餐馆可以视为一个$L\times W$的矩形，其安装了$N$个无线路由器，每个无线路由器给定坐标$x_i,y_i$以及覆盖半径$R_i$（可以安装在餐馆外部）
老板邀请了一位神奇程序员来调整无线路由器的发射倍率（？？？），可以将所有路由器的覆盖半径乘以一个系数$K$，求最小的$K$使得无线覆盖整个餐馆的同时又最节省成本
输入格式
第一行一个整数$T$，表示数据组数
以下$T$组数据，每组数据第一行三个整数$N,L,W$，表示路由器个数和餐馆大小
接下来$N$行，每行三个不超过$1000$的正整数$x_i,y_i,R_i$表示一个路由器的坐标和原始覆盖半径
输出格式
对于每组数据，输出一个实数K，保留3位小数。
样例
样例输入
1 | 1 |
样例输出
1 | 1.414 |
数据范围与提示
数据编号$1$ $N=1$ 数据组数$=20$
数据编号$2$ $N=2$ 数据组数$=20$
数据编号$3$ $N<=10$ 数据组数$=20$
数据编号$4$ $N<=10$ 数据组数$=1000$
数据编号$5$ $N<=50$ 数据组数$=10$
题解
一个极其暴力的暴力……（居然第一题A了那么多人，第三题只有我A了……）
看到这道题，第一眼的思路就是二分
那么我们就看怎么判断是否所有地方都被覆盖了
如果一个矩形，如果它的四个角都被同一个圆覆盖了，那么显然，这整个矩形都被圆覆盖了；如果它的四个角都没有被任何一个圆覆盖，那么显然，这个矩形就完全没有被覆盖；除了上面这两种情况以外的其他情况，我们可以直接暴力地把整个矩形拆成四个小矩形（左上、右上、左下、右下四块），就可以啦！
附上代码：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
struct ppap
{
int x,y;
double R,r;
}a[60];
int n,L,W;
double l,r,eps=1e-6;
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int pd(double x1,double y1,double x2,double y2)
{
if(x2-x1<eps||y2-y1<eps) return 1;
int flag1=0,flag2=0,flag3=0,flag4=0;
for(int i=1;i<=n;i++){
int f1=0,f2=0,f3=0,f4=0;
if(dis(x1,y1,a[i].x,a[i].y)<=a[i].r) flag1=f1=1;
if(dis(x1,y2,a[i].x,a[i].y)<=a[i].r) flag2=f2=1;
if(dis(x2,y2,a[i].x,a[i].y)<=a[i].r) flag3=f3=1;
if(dis(x2,y1,a[i].x,a[i].y)<=a[i].r) flag4=f4=1;
if(f1&&f2&&f3&&f4) return 1;
}
if(!flag1||!flag2||!flag3||!flag4) return 0;
double x3=(x1+x2)/2,y3=(y1+y2)/2;
return pd(x1,y1,x3,y3)&&pd(x3,y3,x2,y2)&&pd(x1,y3,x3,y2)&&pd(x3,y1,x2,y3);
}
int main()
{
freopen("wifi.in","r",stdin);
freopen("wifi.out","w",stdout);
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&L,&W);
for(int i=1;i<=n;i++) scanf("%d%d%lf",&a[i].x,&a[i].y,&a[i].R);
l=0,r=1000.0;
while(l+eps<r){
double mid=(l+r)/2;
for(int i=1;i<=n;i++) a[i].r=a[i].R*mid;
if(pd(0,0,L,W)) r=mid;
else l=mid;
}
printf("%.3lf\n",l);
}
}