首页 > 代码库 > HDU 4717 The Moving Points (三分法)
HDU 4717 The Moving Points (三分法)
题意:给n个点的坐标的移动方向及速度,问在之后的时间的所有点的最大距离的最小值是多少。
思路:三分。两点距离是下凹函数,它们的max也是下凹函数。可以三分。
#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<string>#include<cmath>#include<vector>#define LL long long#define MAXN 100005using namespace std;struct Point{ double x,y,vx,vy; Point(double a,double b,double c,double d):x(a),y(b),vx(c),vy(d) {}};vector<Point> vec;double calc(double time){ double maxn=0; for(int i=0; i<vec.size(); ++i) for(int j=i+1; j<vec.size(); ++j) { double nx=vec[i].x+vec[i].vx*time,ny=vec[i].y+vec[i].vy*time; double mx=vec[j].x+vec[j].vx*time,my=vec[j].y+vec[j].vy*time; maxn=max(maxn,(sqrt((nx-mx)*(nx-mx)+(ny-my)*(ny-my)))); } return maxn;}int main(){ int T,kase=0; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); vec.clear(); for(int i=0;i<n;++i) { double a,b,c,d; scanf("%lf%lf%lf%lf",&a,&b,&c,&d); vec.push_back(Point(a,b,c,d)); } double L=0,R=1e8; for(int i=0; i<100; ++i) { double m1=L+(R-L)/3; double m2=R-(R-L)/3; if(calc(m1)<calc(m2)) R=m2; else L=m1; } printf("Case #%d: %.2lf %.2lf\n",++kase,L,calc(L)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。