Packing polygons

Given a polygon of n points (not necessarily convex), your goal is to say whether there is a circle of a given a radius R that contains the polygon or not.

Input 

The input consists of several input cases. The first line of each input case is the number n (with n < 100) of vertices in the polygon. Then you are given n lines each containing a couple of integers that define the coordinates of the vertices. The last line of the input case will be a real number indicating the radius R of the circle.

The end of the input will be signaled by an input case with n = 0 vertices, that must not be processed.

You may assume that no vertex will appear twice in any given input case.

Output 

If the polygon can be packed in a circle of the given radius you have to print:

The polygon can be packed in the circle.

If the polygon cannot be packed you have to print:

There is no way of packing that polygon.

Sample Input 

3
0 0
1 0
0 1
1.0
3
0 0
1 0
0 1
0.1
0

Sample Output 

The polygon can be packed in the circle.
There is no way of packing that polygon.

---

#include <stdio.h>
#include <math.h>
#define eps 1e-8
struct Point {
    double x, y;
};
double dist(Point &a, Point &b) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
Point circle(Point &a, Point &b, Point &c) {
    static Point ab, ac, o;
    static double a1, b1, c1, a2, b2, c2, D, D1, D2;
    ab.x = (a.x+b.x)/2, ab.y = (a.y+b.y)/2;
    ac.x = (a.x+c.x)/2, ac.y = (a.y+c.y)/2;
    a1 = a.x-b.x, b1 = a.y-b.y;
    c1 = a1*ab.x + b1*ab.y;
    a2 = a.x-c.x, b2 = a.y-c.y;
    c2 = a2*ac.x + b2*ac.y;
    D = a1*b2-a2*b1;
    D1 = c1*b2-c2*b1;
    D2 = a1*c2-a2*c1;
    o.x = D1/D;
    o.y = D2/D;
    return o;
}
double minCoverCircle(Point p[], int n) {
    Point c;
    double cr = 0.0;
    int i, j, k;
    c = p[0];
    for(i = 1; i < n; i++) {
        if(dist(p[i], c) >= cr+eps) {
            c = p[i], cr = 0;
            for(j = 0; j < i; j++) {
                if(dist(p[j], c) >= cr+eps) {
                    c.x = (p[i].x+p[j].x)/2;
                    c.y = (p[i].y+p[j].y)/2;
                    cr = dist(p[i], c);
                    for(k = 0; k < j; k++) {
                        if(dist(p[k], c) >= cr+eps) {
                            c = circle(p[i], p[j], p[k]);
                            cr = dist(p[i], c);
                        }
                    }
                }
            }
        }
    }
    return sqrt(cr);
}

int main() {
    int n, i;
    Point p[100];
    double r, cr;
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++) {
            scanf("%lf %lf", &p[i].x, &p[i].y);
        }
        scanf("%lf", &r);
        cr = minCoverCircle(p, n);
        if(cr > r)
            puts("There is no way of packing that polygon.");
        else
            puts("The polygon can be packed in the circle.");
    }
    return 0;
}