hdu 4071& poj 3873 & zoj 3386 & uva 12197 Trick or Treat 三分法
2024-09-21 13:58:23
思路:
看到这个题目就发现所需最短时间也就是房子和相遇点的最远距离具有凹凸性,很容易就想到了三分法枚举。
找出所有房子的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 ;
}
最新文章
- C语言学习 第七次作业总结
- POJ 2876 Cantoring Along
- 微信小程序配置文件
- C# DES加密
- javascript多重继承
- 狗狗40题~(Volume A)
- jsp 简单下载
- python之旅十【第十篇】paramiko模块
- linux学习笔记2 - linux常用命令
- scheduleAtFixedRate 与 scheduleWithFixedDelay 的区别
- Git 切换本地分支 切换远程分支
- Mybatis使用动态代理实现拦截器功能
- Nestjs 上传文件
- 【转】燃烧吧,TestMice!
- java jdk版本切换
- 基于Apache在本地配置多个虚拟主机站点
- Luogu P1318 积水面积
- create a cocos2d-x-3.0 project in Xcode
- ORACLE默认实例设置--linux
- 禅道 bug指向为数字问题解决过程