本文主要是介绍HDU 4717 The Moving Points(三分枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4717
其实这个题目就是二分枚举的思路，这个应该不用怎么想，因为涉及到这类问题通常都是二分枚举类
这个题目首先想到最大值应该是连续的，而且是个开口向上的抛物线的单调关系，那么在二分枚举的
时候只要想办法确定是向左还是向右就OK了，其实很简单，只要在当前mid的基础上稍微减去一点点
看看是增大了还是变小了，具体见代码！
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <cmath>
using namespace std;
#define maxn 350
#define inf 1e12
#define eps 1e-6
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
int n;
struct point{double x,y,vx,vy;
}po[maxn*maxn];
double dis(point &a,point &b,double t){return sqrt((a.x+a.vx*t-b.x-b.vx*t)*(a.x+a.vx*t-b.x-b.vx*t) + (a.y+a.vy*t-b.y-b.vy*t)*(a.y+a.vy*t-b.y-b.vy*t));
}
double cal_area(double t){double ans=0;int i,j;for(i=0;i<n;i++)for(j=i+1;j<n;j++){ans=MAX(ans,dis(po[i],po[j],t));}return ans;
}
int find_ans(){double l,r,mid;l=0,r=100000000;double ans=inf,temp,temp1,t=inf;while(l < r){// printf("what %lf %lf\n",l,r);mid=(l+r)/2;temp=cal_area(mid);temp1=cal_area(mid-eps);if(temp1 < temp)r=mid-eps;elsel=mid+eps;if(ans > temp)ans=temp,t=mid;}printf("%.2f %.2f\n",t,ans);return 0;
}
int main(){int i,j,k,t,cas=0;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++)scanf("%lf%lf%lf%lf",&po[i].x,&po[i].y,&po[i].vx,&po[i].vy);printf("Case #%d: ",++cas);find_ans();}return 0;
}这篇关于HDU 4717 The Moving Points(三分枚举)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
