[bzoj2517]矩形覆盖
2024-10-19 07:53:55
Description
给定一个$l\;\times\;w$的矩形,和$n$个圆,求最小的$k$使得每个圆的半径$\;\times\;k$后,能覆盖整个矩形.
Input
第一行一个整数$T$,表示数据组数.
以下$T$组数据,每组数据第一行三个整数$N,L,W$,表示圆个数和矩形大小.
接下来$N$行,每行三个正整数$x[i],y[i],R[i]$表示一个圆心的坐标和原始半径.
Output
对于每组数据,输出一个实数$K$,保留$3$位小数.
Sample Input
1
1 2 2
1 1 1
Sample Output
1.414
HINT
$t\;\leq\;10,n\;\leq\;50,x[i],y[i],R[i]\;\leq\;1000$
Solution
二分$k$,分治矩形判断当前$k$是否可行:
$1.$如果当前矩形的四个顶点在同一圆内,可行;
$2.$如果当前矩形有一个顶点不在圆内,不可行;
$3.$如果当前矩形的四个顶点不在同一圆内,分成$4$部分继续判断.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 55
#define K 1e-7
#define eps 1e-13
using namespace std;
int n,t;
double a[N],x[N],y[N],r[N],l,w,lef,rig,mid;
inline double sqr(double x){
return x*x;
}
inline bool in(int i,double k,double n,double m){
double d=sqr(x[i]-n)+sqr(y[i]-m);
return d<=sqr(r[i])+eps;
}
inline bool chk(double k,double n1,double n2,double m1,double m2){
bool f1=0,f2=0,f3=0,f4=0;
if(fabs(n1-n2)<eps&&fabs(m1-m2)<eps) return true;
for(int i=1,l1,l2,l3,l4;i<=n;++i){
l1=in(i,k,n1,m1);l2=in(i,k,n1,m2);
l3=in(i,k,n2,m1);l4=in(i,k,n2,m2);
if(l1&&l2&&l3&&l4) return true;
f1|=l1;f2|=l2;f3|=l3;f4|=l4;
}
if(!f1||!f2||!f3||!f4) return false;
double mm=(m1+m2)*0.5,nn=(n1+n2)*0.5;
return chk(k,n1,nn,m1,mm)&&chk(k,n1,nn,mm,m2)\
&&chk(k,nn,n2,m1,mm)&&chk(k,nn,n2,mm,m2);
}
inline void Aireen(){
scanf("%d",&t);
while(t--){
scanf("%d%lf%lf",&n,&l,&w);
for(int i=1;i<=n;++i)
scanf("%lf%lf%lf",&x[i],&y[i],&a[i]);
lef=0.0;rig=l+w;
while(lef+K<rig){
mid=(lef+rig)*0.5;
for(int i=1;i<=n;++i)
r[i]=a[i]*mid;
if(chk(mid,0.0,l,0.0,w)) rig=mid;
else lef=mid+K;
}
printf("%.3lf\n",lef);
}
}
int main(){
freopen("cover.in","r",stdin);
freopen("cover.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
最新文章
- Android 配置问题
- win7升级为Win10 10586版本,出现应用商店打不开的解决办法
- Unity3d 鼠标拣选小功能集合
- EBS 密码相关
- python ssh
- HDU 5629 Clarke and tree dp+prufer序列
- java 设计模式初探之适配器模式
- IPython在Windows 7上的搭建步骤
- csu1306: Manor
- KB奇遇记(1):开篇
- LINUX下解决TIME_WAIT等网络问题
- HDU5816 Hearthstone
- Android软件设计规范---命名规则/代码包设计规则等
- Docker:bash: vi: command not found
- iOS-Xcode解决【workspace integrity couldn&#39;t load project&#39;】
- Error Installing Tivoli Directory Server (TDS) for TNPMW1.3
- Hibernate 应知应会
- C++ operator关键字
- PLSQLDeveloper安装与配置
- 面经问题总结——django相关
热门文章
- nginx反向代理tomcat访问时浏览器加载失败,出现 ERR_CONTENT_LENGTH_MISMATCH 问题
- PAT 1004. 成绩排名 (20)
- Typescript 其实就想排个序和枚举取数
- 15个nosql数据库
- salt基本原理
- C#——Marshal.StructureToPtr方法简介
- java:利用xpath删除xml中的空节点
- 高性能JavaScript DOM编程
- 【开源】LLMAnimator 60多种动画让你的应用动起来
- LaTeX常用数学符号表示方法