淘先锋技术网

首页 1 2 3 4 5 6 7

hdu 4717 The Moving Points（三分+计算几何）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4717

说明下为啥满足三分：

设y=f(x) （x>0)表示任意两个点的距离随时间x的增长，距离y的变化。则f(x)函数单调性有两种：1.先单减，后单增。2.一直单增。 

设y=m(x) (x>0)表示随时间x的增长，所有点的最大距离y的变化。即m(x)是所有点对构成的f(x)图像取最上面的部分。则m(x)的单调性也只有两种可能：1.先单减，后单增。2.一直单增。 这个地方的证明可以这样：假如时刻t1到时刻t2最大值取得是函数f1(x)的图像，在时刻t2到时刻t3取得是f2(x)的图像，

 

那么由图可以看出f2(x)的斜率大于f1(x)的斜率

可以归纳出m(x)函数的斜率是递增。那么单调性就可以知道了。

m(x)有了上面的性质，就可以有三分了。

 

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const double eps = 1e-8;
const double PI = acos(-1.0);
const double INF = 1000000000000000.000;

struct Point{
    double x,y;
    Point(double x=0, double y=0) : x(x),y(y){ }    //构造函数
};
typedef Point Vector;

Vector operator + (Vector A , Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Vector A , Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (double p,Vector A){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);}

bool operator < (const Point& a,const Point& b){
    return a.x < b.x ||( a.x == b.x && a.y < b.y);
}

int dcmp(double x){
    if(fabs(x) < eps) return 0;
    else              return x < 0 ? -1 : 1;
}
bool operator == (const Point& a, const Point& b){
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

///向量（x,y）的极角用atan2(y,x);
inline double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }
inline double Length(Vector A)    { return sqrt(Dot(A,A)); }
inline double Angle(Vector A, Vector B)  { return acos(Dot(A,B) / Length(A) / Length(B)); }

Point read_point(){
    Point A;
    scanf("%lf %lf",&A.x,&A.y);
    return A;
}

/*************************************分 割 线*****************************************/
const int maxn = 305;

Point P[maxn];
Vector V[maxn];
int N;

double calMax(double t){
    double ret = 0;
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++){
            double len = Length(P[i]+t*V[i]-(P[j]+t*V[j]));
            ret = max(ret,len);
    }
    return  ret;
}

int main()
{
    //freopen("E:\\acm\\input.txt","r",stdin);
    int T;
    cin>>T;
    for(int cas=1;cas<=T;cas++){
        cin>>N;
        for(int i=1;i<=N;i++){
            P[i] = read_point();
            V[i] = read_point();
        }

        double Lt=0;
        double Rt=1e7;

        double M1t,M1w;
        double M2t,M2w;
        while(dcmp(Rt-Lt)>0){
            M1t = Lt+(Rt-Lt)/3;
            M1w = calMax(M1t);

            M2t = Lt+(Rt-Lt)/3*2;
            M2w = calMax(M2t);

            if(dcmp(M1w-M2w)>=0){
                Lt = M1t+eps;
            }
            else{
                Rt = M2t-eps;
            }
        }
        printf("Case #%d: %.2lf %.2lf\n",cas,Lt,calMax(Lt));
    }
}
View Code

 

 

转载于:https://www.cnblogs.com/acmdeweilai/p/3315769.html