[UVa] 12197 - Trick or Treat

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12197 - Trick or Treat
Source            : UVa Online Judge
Category          : Search, Geometry
Algorithm         : Ternary Search
Verdict           : Accepted

#include <bits/stdc++.h>  
   
using namespace std;  
   
static const int MAXN = 50000 + 5;  
   
struct Point  
{  
    double x, y;  
    Point() {}  
    Point(double x, double y)  
    {  
        this->x = x;  
        this->y = y;  
    }  
    double dist(Point p)  
    {  
        return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));  
    }  
};  
   
Point point[MAXN];  
   
double f(Point p, int n)  
{  
    double maxi = -1e12;  
    for (int i = 1; i <= n; i++)  
    {  
        double dis = point[i].dist(p);  
        if (dis > maxi) maxi = dis;  
    }  
    return maxi;  
}  
   
void ternary_search(int n)  
{  
    Point a, b, aa, bb;  
    a =  {-200005, 0};  
    b = {200005, 0};  
    double mini = 1e12 + 6;  
    for (int it = 0; it < 300; it++)  
    {  
        aa.x = a.x + (b.x - a.x) / 3.0;  
        aa.y = 0;  
        bb.x = b.x - (b.x - a.x) / 3.0;  
        bb.y = 0;  
        double mid1 = f(aa, n);  
        double mid2 = f(bb, n);  
        mini = min(mini, min(mid1, mid2));  
        if (mid1 < mid2) b = bb;  
        else a = aa;  
    }  
    cout << fixed << setprecision(5) << aa.x << " " << mini << endl;  
}  
   
int main()  
{  
    int n;  
    while (cin >> n, n)  
    {  
        for (int i = 1; i <= n; i++)  
            cin >> point[i].x >> point[i].y;  
        ternary_search(n);  
    }  
}