题目链接

第一次写三分

三分的基本模板

int SanFen(int l,int r) //找凸点
{
while(r-l>)
{
//mid为中点,midmid为四等分点
int mid = (l+r)/;
int midmid = (mid+r)/;
if( f(mid) > f(midmid) )
r = midmid;
else
l = mid;
}
return f(l) > f(r) ? l : r;
}

这道题里面任意两点的距离都可以看作是一个凹函数,对任意t对所有凹函数取最大值构成一个新的凹函数,求新函数的最小值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; const int N=;
const double eps=1e-; int T,n;
double tim,mindis; struct point
{
double x,y;
int dx,dy;
}p[N]; double dist(point p1,point p2,double t)
{
double x2=(p1.x+t*p1.dx-p2.x-t*p2.dx)*(p1.x+t*p1.dx-p2.x-t*p2.dx);
double y2=(p1.y+t*p1.dy-p2.y-t*p2.dy)*(p1.y+t*p1.dy-p2.y-t*p2.dy);
return sqrt(x2+y2);
} double cal(double x)
{
double ret=-;
for(int i=;i<n;i++)
for(int j=i+;j<n;j++)
ret=max(ret,dist(p[i],p[j],x));
return ret;
} void solve()
{
double l=,r=1e8;
while(r-l>eps)
{
double mid=(l+r)/;
double midmid=(mid+r)/;
double ans1=cal(mid);
double ans2=cal(midmid);
if(ans1>ans2) l=mid;
else r=midmid;
}
tim=l;
mindis=cal(tim);
} int main()
{
scanf("%d",&T);
for(int kase=;kase<=T;kase++)
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%lf%lf%d%d",&p[i].x,&p[i].y,&p[i].dx,&p[i].dy);
solve();
printf("Case #%d: %.2lf %.2lf\n",kase,tim,mindis);
}
}

最新文章

  1. iOS中UIMenuController的使用
  2. NodeJs - 100
  3. 文明3地图之二-大n型地图
  4. 1.mybatis简介
  5. Word2007插入两种页码
  6. 【Linux高频命令专题(7)】rm
  7. C# 上传excel文档解析出里面数据
  8. java对Ldap操作4
  9. MapReduce优化
  10. QRMaker生成二维码,支持中文
  11. QT国际化
  12. openwrt ramips随记
  13. bind启动时提示953端口被使用
  14. NLog使用整理
  15. ubuntu环境下安装docker遇到的坑
  16. JPA核心类与使用
  17. MySQL 导出用户权限
  18. Undertow的InMemorySessionManager
  19. 2018/09/13《涂抹MySQL》【MySQL复制特性】学习笔记(六)
  20. 《Java设计模式》之模板方法模式

热门文章

  1. python中有哪些类型的布尔值是False?
  2. IPv6 首部格式
  3. 使用NHibernate连接MySQL数据库及增删改查
  4. Linux-档案权限概念
  5. hive重要命令
  6. vue --》watch 深度监听的优化。
  7. SVG.JS 画弧线
  8. docker--docker版本以及安装
  9. PPT制作,数据图等画图
  10. 漫漫人生路,我们该何去何从! Python让我找到了方向