首页 > 代码库 > zoj 3386 Trick or Treat 三分 求最大值的 最小值

zoj 3386 Trick or Treat 三分 求最大值的 最小值

2024-07-04 14:30:12   227人阅读

题目来源：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3963

题意：  给定 N 个不同的点， 求在x轴上的 一点，  使 这点到N个点的 距离 最大 的 最小值。

f(x) =  max(i){ (xi - x) ^2 + yi ^2 }

求 x  使  min(f(x)) ， f(x)为凹函数   ，  采用三分的形式

代码如下：

const double EPS = 1e-10 ;
const int Max_N =  50005 ;
int n;
double add(double a, double b){
    return (fabs(a + b) < EPS * (fabs(a) + fabs(b))) ? 0 : (a + b) ;
}
struct Point {
    double x, y;
    double dist(double a){
        return sqrt(add((x - a)*(x -a) ,(y)*(y) )) ;
    }
};
Point pt[Max_N] ;
double f(double x){
    int i ;
    double Max = 0 ;
    for( i = 0  ; i <  n;  i++){
        Max = pt[i].dist(x) > Max ? pt[i].dist(x) : Max ;
    }
    return Max ;
}
double tri_search(){
    double Mid, Midmid , L,  R ;
    L = -400000.0  , R = 400000.0 ;
    while(L + EPS < R){
        Mid = (L + R) * 0.5 ;
        Midmid = (Mid + R) *0.5 ;
        if(f(Mid) <= f(Midmid ) )
            R = Midmid ;
        else L = Mid ;
    }
    return L ;
}
int main(){
    while(scanf("%d", &n) && n){
        for(int i =0 ; i < n ; i++)
            scanf("%lf%lf" , &pt[i].x ,&pt[i].y ) ;
        double xx = tri_search() ;
        double Max = f(xx) ;
        printf("%.9lf %.9lf\n" , xx + EPS , Max) ;
    }
}

 


联系
我们