思路:

看到这个题目就发现所需最短时间也就是房子和相遇点的最远距离具有凹凸性,很容易就想到了三分法枚举。

找出所有房子的X坐标的最小最大值作为上下界。

代码如下:

 #include<stdio.h>
#include<math.h>
#include<algorithm>
#define M 50005
#include<iostream>
#define inf 200005
#define eps 1e-8
using namespace std;
struct node
{
double x,y;
}p[M];
int n,cnt;
double dis(node a,double b)
{
return sqrt((a.x-b)*(a.x-b)+a.y*a.y);
}
double cal(double a)
{
double ans=;
for(int i=;i<n;i++){
double t=dis(p[i],a);
if(ans<t) ans=t;
}
return ans;
}
int main()
{
double l,r,m,mm;
while(scanf("%d",&n)&&n){
l=inf;r=-inf;
for(int i=;i<n;i++){
scanf("%lf %lf",&p[i].x,&p[i].y);
if(p[i].x<l) l=p[i].x;
if(p[i].x>r) r=p[i].x;
}
while(r-l>=eps){
m=(l+r)/;
mm=(l+m)/;
double t=cal(m);
double tt=cal(mm);
if(t>=tt) r=m;
else l=mm;
}
printf("%.9lf %.9lf\n",r,cal(r));
}
return ;
}

最新文章

  1. C语言学习 第七次作业总结
  2. POJ 2876 Cantoring Along
  3. 微信小程序配置文件
  4. C# DES加密
  5. javascript多重继承
  6. 狗狗40题~(Volume A)
  7. jsp 简单下载
  8. python之旅十【第十篇】paramiko模块
  9. linux学习笔记2 - linux常用命令
  10. scheduleAtFixedRate 与 scheduleWithFixedDelay 的区别
  11. Git 切换本地分支 切换远程分支
  12. Mybatis使用动态代理实现拦截器功能
  13. Nestjs 上传文件
  14. 【转】燃烧吧,TestMice!
  15. java jdk版本切换
  16. 基于Apache在本地配置多个虚拟主机站点
  17. Luogu P1318 积水面积
  18. create a cocos2d-x-3.0 project in Xcode
  19. ORACLE默认实例设置--linux
  20. 禅道 bug指向为数字问题解决过程

热门文章

  1. MS16-032提权正确方法
  2. xrange和range的区别
  3. linux子系统的初始化_subsys_initcall()【转】
  4. Visual Studio 附加到进程调试
  5. JavaScript里的小妖精
  6. JavaScript知识点的总结
  7. Java将CST的时间字符串转换成需要的日期格式字符串
  8. vsftpd 虚拟用户配置
  9. CSS3新属性解释及用法
  10. linux命令(20):rm命令