## Algorithm

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.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

`````` #include

using namespace std;
#define EPS 1e8

struct point {
double x, y;
point() { x = y = 0.0; }
point(double _x, double _y) : x(_x), y(_y) {}
bool operator < (point other) const { // override less than operator
if (fabs(x - other.x) > EPS) // useful for sorting
return x < other.x; // first criteria , by x-coordinate
return y < other.y;
}
};

double dist(point p1, point p2) { // Euclidean distance
// hypot(dx, dy) returns sqrt(dx * dx + dy * dy)
return hypot(p1.x - p2.x, p1.y - p2.y);
}

bool circle2PtsRad(point p1, point p2, double r, point &c) {
double d2 = (p1.x - p2.x) * (p1.x - p2.x) +
(p1.y - p2.y) * (p1.y - p2.y);
double det = r * r / d2 - 0.25;
if (det < 0.0) return false;
double h = sqrt(det);
c.x = (p1.x + p2.x) * 0.5 + (p1.y - p2.y) * h;
c.y = (p1.y + p2.y) * 0.5 + (p2.x - p1.x) * h;
return true;
}

int main() {
int n;
point c;
while(scanf("%d",&n), n){
vector polygon;
for(int i=0;i rad) foundCircle = false;
}
}
if(foundCircle) printf("The polygon can be packed in the circle.\n");
else printf("There is no way of packing that polygon.\n");
}
}``````
Copy The Code &

Input

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

Output

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

## Demonstration

UVA Online Judge solution - 10005 - Packing polygons - UVA online judge solution in C,C++,Java