HDU4714+三分

题意：给定N个点，每个点有初始位置和初始速度。

问：在哪个时刻使得所有的点的最大距离值最小。

分析：一开始枚举两两之间的最大值，然后在最大值中求一个最小值。。。（WA：题意严重理解不清。。）

由两点之间的距离公式（与T一个系数有关）可知，这个公式是典型的抛物线，因此可以进行三分查找答案，正解！

 /*

 wa

 */

 #include<algorithm>

 #include<iostream>

 #include<string.h>

 #include<stdlib.h>

 #include<stdio.h>

 #include<math.h>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long int64;

 //typedef __int64 int64;

 typedef pair<int64,int64> PII;

 #define MP(a,b) make_pair((a),(b))

 const double inf =  9999999999.0;

 const double inf2 = 1.0*(1e8);

 const double pi=acos(-1.0);

 const int dx[]={,-,,};

 const int dy[]={,,,-};

 const double eps = 1e-;

 const int maxm = ;

 const int maxn = ;  

 struct NODE{

     double t,d;

 }mat[ maxn ][ maxn ];

 struct Point{

     double x,y;

     double vx,vy;

 }pnt[ maxn ];

 double solve( double t,int n ){

     double dis = ;

     for( int i=;i<n;i++ ){

         for( int j=i+;j<n;j++ ){

             dis = max( dis, (pnt[i].x-pnt[j].x+pnt[i].vx*t-pnt[j].vx*t)*(pnt[i].x-pnt[j].x+pnt[i].vx*t-pnt[j].vx*t)+(pnt[i].y-pnt[j].y+pnt[i].vy*t-pnt[j].vy*t)*(pnt[i].y-pnt[j].y+pnt[i].vy*t-pnt[j].vy*t) );

         }

     }

     return sqrt(dis);

 }

 int main(){

     int T;

     int ca = ;

     scanf("%d",&T);

     while( T-- ){

         int n;

         scanf("%d",&n);

         for( int i=;i<n;i++ ){

             scanf("%lf%lf%lf%lf",&pnt[ i ].x,&pnt[ i ].y,&pnt[ i ].vx,&pnt[ i ].vy);

         }

         double L = ;

         double R = inf2;

         double ans_d = inf;

         double ans_t = inf;

         while( L+eps<R ){

             double mid1 = ( L+R )/2.0;

             double mid2 = ( mid1+R )/2.0;

             double d1 = solve( mid1,n );

             double d2 = solve( mid2,n );

             if( d1<=d2 ) {

                 if( d1<ans_d ){

                     ans_t = mid1 ;

                     ans_d = d1;

                 }

                 else if( d1==ans_d )

                     ans_t = min( ans_t,mid1 );

                 R = mid2;

             }

             else {

                 if( d2<ans_d ){

                     ans_t = mid2 ;

                     ans_d = d2;

                 }

                 else if( d2==ans_d )

                     ans_t = min( ans_t,mid2 );

                 L = mid1;

             }

             //printf("L = %lf,R = %lf\n",L,R);

         }

         printf("Case #%d: %.2lf %.2lf\n",ca++,ans_t,ans_d);

     }

     return ;

 }

巴特西

HDU4714+三分

最新文章

热门文章