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

题目来源：

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) ;} }

 

转载于:https://www.cnblogs.com/zn505119020/p/3729693.html

总结

以上是生活随笔为你收集整理的zoj 3386 Trick or Treat 三分 求最大值的 最小值的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。