2012-05-13 21:40:05Morris
[UVA][最小覆蓋圓] 10005 - Packing polygons
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.
| Packing polygons |
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;
}