首页 > 代码库 > hdu 4717 The Moving Points(三分)
hdu 4717 The Moving Points(三分)
题目链接:hdu 4717 The Moving Points
题意:
在二维平面上有n个点,每个点给出移动的方向和速度。
问在某个时刻,这些点中最大距离最小是多少,输出时刻和距离。
题解:
我们可以知道,每个点对的距离要么是单调递增,要么是有一个峰的函数。
举例画一下可知道合成的这个函数最多只有一个峰,所以可以用三分求解。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=307; 6 int t,n,cas; 7 double X[N],Y[N],VX[N],VY[N]; 8 9 double dis(double a,double b,double c,double d){return sqrt((c-a)*(c-a)+(d-b)*(d-b));} 10 11 double check(double time) 12 { 13 double mx=0; 14 F(i,1,n)F(j,1,n) 15 mx=max(mx,dis(X[i]+time*VX[i],Y[i]+time*VY[i],X[j]+time*VX[j],Y[j]+time*VY[j])); 16 return mx; 17 } 18 19 int main(){ 20 scanf("%d",&t); 21 while(t--) 22 { 23 scanf("%d",&n); 24 F(i,1,n)scanf("%lf%lf%lf%lf",X+i,Y+i,VX+i,VY+i); 25 double l=0,r=1e7,mid,mmid; 26 F(i,1,100) 27 { 28 mid=(l+r)/2,mmid=(mid+r)/2; 29 if(check(mid)<check(mmid))r=mmid;else l=mid; 30 } 31 printf("Case #%d: ",++cas); 32 check(l)>check(r)?printf("%.2f %.2f\n",l,check(l)):printf("%.2f %.2f\n",r,check(r)); 33 } 34 return 0; 35 }
hdu 4717 The Moving Points(三分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。