hdu 4717: The Moving Points 【三分】
2024-08-24 11:43:55
第一次写三分
三分的基本模板
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);
}
}
最新文章
- iOS中UIMenuController的使用
- NodeJs - 100
- 文明3地图之二-大n型地图
- 1.mybatis简介
- Word2007插入两种页码
- 【Linux高频命令专题(7)】rm
- C# 上传excel文档解析出里面数据
- java对Ldap操作4
- MapReduce优化
- QRMaker生成二维码,支持中文
- QT国际化
- openwrt ramips随记
- bind启动时提示953端口被使用
- NLog使用整理
- ubuntu环境下安装docker遇到的坑
- JPA核心类与使用
- MySQL 导出用户权限
- Undertow的InMemorySessionManager
- 2018/09/13《涂抹MySQL》【MySQL复制特性】学习笔记(六)
- 《Java设计模式》之模板方法模式