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

說(shuō)明下為啥滿足三分：

設(shè)y=f(x) （x>0)表示任意兩個(gè)點(diǎn)的距離隨時(shí)間x的增長(zhǎng)，距離y的變化。則f(x)函數(shù)單調(diào)性有兩種：1.先單減，后單增。2.一直單增。?

設(shè)y=m(x) (x>0)表示隨時(shí)間x的增長(zhǎng)，所有點(diǎn)的最大距離y的變化。即m(x)是所有點(diǎn)對(duì)構(gòu)成的f(x)圖像取最上面的部分。則m(x)的單調(diào)性也只有兩種可能：1.先單減，后單增。2.一直單增。 這個(gè)地方的證明可以這樣：假如時(shí)刻t1到時(shí)刻t2最大值取得是函數(shù)f1(x)的圖像，在時(shí)刻t2到時(shí)刻t3取得是f2(x)的圖像，

?

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

可以歸納出m(x)函數(shù)的斜率是遞增。那么單調(diào)性就可以知道了。

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

?

#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){ } //構(gòu)造函數(shù) }; 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

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/acmdeweilai/p/3315769.html

總結(jié)

以上是生活随笔為你收集整理的hdu 4717 The Moving Points（三分+计算几何）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。