Dezider's Coverup

Question

Zlatica to his house for dinner. The trouble is, he tripped with the sauce in his hands (thankfully this was in the morning and Zlatica did not see it) and many bright red droplets fell on his white carpet. Now Dezider is starting to panic because he wants to have a perfectly clean house to impress Zlatica. Fortunately, there is a store nearby which sells all sizes of (expensive) circular rugs. Dezider does not have much money so he wants to buy the smallest rug with an integer radius which will cover all the droplets. You need to write a program to help him determine the right size to buy.

Input

Each test cases starts with one positive integer n, the number of droplets on the carpet. Each of the following n lines contains two floating-point numbers, separated by white space, which represent the x- and y-coordinate of the corresponding droplet.

Output

One line for each test case which consists of a single integer, the radius of the smallest circular rug needed to cover all the droplets.

Sample Input

4
1 -0.5
1.5 0
0.5 0.5
1 0.5

Sample Output

1

Answer 1

#include
#include
#include

using namespace std;

const double eps = 1e-8;

template
struct Point
{
T x, y;
Point() { }
Point(T x, T y) : x(x), y(y) { }
};

template
bool operator <(const Point& lhs, const Point& rhs)
{
return (lhs.y != rhs.y) ? lhs.y < rhs.y : lhs.x < rhs.x;
}

template
Point operator -(const Point& lhs, const Point& rhs)
{
return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

template
T xmult(const Point& lhs, const Point& rhs)
{
return lhs.x * rhs.y - lhs.y * rhs.x;
}

template
int GrahamScan(int n, Point p[], Point ret[], bool all = false)
{
const double eps = all ? ::eps : -::eps;
int sp, tmp;

if (n < 3) {
    for (int i = 0; i < n; i++) {
        ret[i] = p[i];
    }
    return n;
}
sort(p, p + n);
ret[0] = p[0];
ret[1] = p[1];
sp = 2;
for (int i = 2; i < n; i++) {
    while (sp > 1 && xmult(ret[sp - 1] - ret[sp - 2], p[i] - ret[sp - 2]) > eps) {
        --sp;
    }
    ret[sp++] = p[i];
}
tmp = sp;
ret[sp++] = p[n - 2];
for (int i = n - 3; i >= 0; i--) {
    while (sp > tmp && xmult(ret[sp - 1] - ret[sp - 2], p[i] - ret[sp - 2]) > eps) {
        --sp;
    }
    ret[sp++] = p[i];
}

return sp - 1;

}

inline double sqr(const double& x)
{
return x * x;
}

inline double dd(const Point& a, const Point& b)
{
return sqr(a.x - b.x) + sqr(a.y - b.y);
}

double getDD(const Point& a, const Point& b, const Point& c)
{
double da = dd(b, c), db = dd(a, c), dc = dd(a, b);

if (da + 1e-8 >= db + dc) return da;
if (db + 1e-8 >= da + dc) return db;
if (dc + 1e-8 >= da + db) return dc;

return dc / (1.0 - sqr(da + db - dc) / (4 * da * db));

}

Point pp[1024], p[1024];

int main()
{
int n;
double d2, tmp, ans;

while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &pp[i].x, &pp[i].y);
    }
    n = GrahamScan(n, pp, p);
    if (n <= 1) {
        ans = 0;
    }
    else if (n == 2) {
        ans = dd(p[0], p[1]);
    }
    else {
        ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ans = max(ans, getDD(p[i], p[j], p[k]));
                }
            }
        }
    }
    printf("%.0lf\n", ceil(sqrt(ans) / 2.0 - 1e-8) + 1e-8);
}

return 0;

}