Time Limit: 6000/3000 MS
(Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 964 Accepted
Submission(s): 393
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <math.h> 5 #include <algorithm> 6 using namespace std; 7 #define eps 0.000001 8 typedef struct abcd 9 { 10 double x,y,vx,vy; 11 } point; 12 point p[400]; 13 int n; 14 double dis(double tt,int x,int y) 15 { 16 double xx=p[x].x+tt*p[x].vx; 17 double yy=p[x].y+tt*p[x].vy; 18 double xx1=p[y].x+tt*p[y].vx; 19 double yy1=p[y].y+tt*p[y].vy; 20 return sqrt((xx-xx1)*(xx-xx1)+(yy-yy1)*(yy-yy1)); 21 } 22 double funa(double tt) 23 { 24 int i,j; 25 double maxa=0; 26 for(i=0;i<n;i++) 27 { 28 for(j=i+1;j<n;j++) 29 { 30 maxa=max(maxa,dis(tt,i,j)); 31 } 32 } 33 //cout<<tt<<endl; 34 return maxa; 35 } 36 double fun() 37 { 38 double l=0,r=210000000,m1,m2; 39 while(r-l>eps) 40 { 41 m1=l+(r-l)/3; 42 m2=r-(r-l)/3; 43 if(funa(m1)<funa(m2)) 44 { 45 r=m2; 46 } 47 else l=m1; 48 } 49 return l; 50 } 51 int main() 52 { 53 int t,i,j,k; 54 scanf("%d",&t); 55 for(i=1; i<=t; i++) 56 { 57 scanf("%d",&n); 58 for(j=0; j<n; j++) 59 { 60 scanf("%lf%lf%lf%lf",&p[j].x,&p[j].y,&p[j].vx,&p[j].vy); 61 } 62 double yyy=fun(); 63 printf("Case #%d: %.2lf %.2lf\n",i,yyy,funa(yyy)); 64 } 65 }
The Moving Points hdu4717,布布扣,bubuko.com
原文:http://www.cnblogs.com/ERKE/p/3637096.html