#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; typedef long long LL; #define CLR(x,y) memset((x),(y),sizeof((x))) const int maxn = 50000 + 100; int n; struct Point{ double x,y; bool operator < (const Point a)const { return a.x > x; } }p[maxn]; double Calc(double x) { double rtn = 0; for(int i = 0 ; i < n ;++i){ rtn = max(rtn , sqrt(double(p[i].y * p[i].y + (p[i].x - x) * (p[i].x - x)))); } return rtn; } double Solve(double MIN, double MAX) { double Left, Right; double mid = 0, midmid = 0; double mid_area = 0, midmid_area = 0; Left = MIN; Right = MAX; for(int i = 0;i < 150;++i){ mid = (Left + Right) / 2; midmid = (mid + Right) / 2; mid_area = Calc(mid); midmid_area = Calc(midmid); if (midmid_area - mid_area > eps) Right = midmid; else Left = mid; } return midmid; } int main(){ while(~scanf("%d",&n) && n){ for(int i = 0;i < n ;++i) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p,p+n); double res = Solve(p[0].x,p[n - 1].x); printf("%.7lf %.7lf\n",res,Calc(res)); } return 0; } |
[2016-03-05][UVALive][4504][Trick or Treat]
原文：http://www.cnblogs.com/qhy285571052/p/5245945.html