[Light OJ] 1146 - Closest Distance

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1146 - Closest Distance
Source            : Light Online Judge
Category          : Search, Geometry
Algorithm         : Ternary Search
Verdict           : Accepted 

#include <bits/stdc++.h>
 
using namespace std;
 
struct point
{
    double x, y;
    point() {}
    point(double x, double y)
    {
        this->x = x;
        this->y = y;
    }
    double dist(point p)
    {
        p.x -= x, p.y -= y;
        return sqrt(p.x*p.x + p.y*p.y);
    }
    void input()
    {
        double xx, yy;
        cin >> xx >> yy;
        x = xx;
        y = yy;
    }
    void divide_1(point p, point q)
    {
        x = p.x + (q.x-p.x)/3.0;
        y = p.y + (q.y-p.y)/3.0;
    }
    void divide_2(point p, point q)
    {
        x = q.x - (q.x-p.x)/3.0;
        y = q.y - (q.y-p.y)/3.0;
    }
 
} a, b, c, d;
 
double ternary_search()
{
    point aa, bb, cc, dd;
    double ans = 1e12 + 7;
    for (int tol = 0; tol < 300; tol++)
    {
        aa.divide_1(a, b);
        bb.divide_2(a, b);
        cc.divide_1(c, d);
        dd.divide_2(c, d);
        double fA = aa.dist(cc);
        double fB = bb.dist(dd);
        ans = min(ans, min(fA, fB));
        if (fA > fB)
            a = aa, c = cc;
        else
            b = bb, d = dd;
    }
    return ans;
}
 
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        a.input();
        b.input();
        c.input();
        d.input();
        cout << "Case " << tcase << ": "
             << fixed << setprecision(6) << ternary_search() << "\n";
    }
}