HDU 4717 The Moving Points 三分

http://acm.hdu.edu.cn/showproblem.php?pid=4717

显然最大距离是凸函数,三分时间即可

/********************* Template ************************/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define BUG         cout<<" BUG! "<<endl;
#define LINE        cout<<" ------------------ "<<endl;
#define FIN         freopen("in.txt","r",stdin);
#pragma comment     (linker,"/STACK:102400000,102400000")
template<class T> inline T L(T a)       {return (a << 1);}
template<class T> inline T R(T a)       {return (a << 1 | 1);}
template<class T> inline T lowbit(T a)  {return (a & -a);}
template<class T> inline T Mid(T a,T b) {return ((a + b) / 2);}
template<class T> inline T gcd(T a,T b) {return b ? gcd(b,a%b) : a;}
template<class T> inline T lcm(T a,T b) {return a / gcd(a,b) * b;}
template<class T> inline T Min(T a,T b) {return a < b ? a : b;}
template<class T> inline T Max(T a,T b) {return a > b ? a : b;}
template<class T> inline T Min(T a,T b,T c)     {return min(min(a,b),c);}
template<class T> inline T Max(T a,T b,T c)     {return max(max(a,b),c);}
template<class T> inline T Min(T a,T b,T c,T d) {return min(min(a,b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d) {return max(max(a,b),max(c,d));}
template<class T> inline void mem(T &a,int b)   {memset(a,b,sizeof(a));}
template<class T> inline T exGCD(T a, T b, T &x, T &y){ //
    if(!b) return x = 1,y = 0,a;
    T res = exGCD(b,a%b,x,y),tmp = x;
    x = y,y = tmp - (a / b) * y;
    return res;
}
typedef long long LL;    typedef unsigned long long ULL;
//typedef __int64 LL;      typedef unsigned __int64 ULL;
const LL LINF   = 1LL << 60;
const int MOD   = 1000000007;
const int INF   = 0x7fffffff;
const int MAXN  = 300+5;//(int)1e6+5;
const double EPS    = 1e-8;
const double DINF   = 1e15;
const double PI     = acos(-1.0);

/*********************   By  F   *********************/
struct POINT{
    double x,y;
    double vx,vy;
}p[MAXN];
int n;
double dist(POINT a,POINT b,double t){
    double ax = a.x + t * a.vx;
    double ay = a.y + t * a.vy;
    double bx = b.x + t * b.vx;
    double by = b.y + t * b.vy;
    return sqrt((ax-bx) * (ax-bx) + (ay-by) * (ay-by));
}
double mindist(double t){
    double res = -DINF;
    for(int i = 0 ; i < n ; i++)
        for(int j = i+1 ; j < n ; j++)
            res = max(dist(p[i],p[j],t),res);
    return res;
}
pair<double,double> tri_search(double l,double r){
    double mid,midmid;
    while(l+EPS < r){
        mid = (l+r)/2;
        midmid = (mid+r)/2;
        double mid_ans = mindist(mid);
        double midmid_ans = mindist(midmid);
        if(mid_ans >= midmid_ans) l = mid;
        else r = midmid;
    }
    return make_pair(l,mindist(l));
}
int main(){
    int T;
    cin>>T;
    for(int t = 1 ; t <= T ;t++){
        cin>>n;
        for(int i = 0 ; i < n ; i++)
            scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].vx,&p[i].vy);
        pair<double,double> p = tri_search(0,1e6);
        printf("Case #%d: %.2lf %.2lf
",t,p.first,p.second);
    }
    return 0;
}