Algorithm


 problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=946 

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 <bits/stdc++.h>

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;
    double rad;
    point c;
    while(scanf("%d",&n), n){
        vector < point> polygon;
        for(int i=0;i < n;i++) {
            point p;
            scanf("%lf %lf",&p.x,&p.y);
            polygon.push_back(p);
        }
        scanf("%lf",&rad);
        bool foundCircle = false;
        for(int i=0;i < n && !foundCircle;i++){
            for(int j=0;j < n && !foundCircle;j++){
                if(i==j) continue;
                circle2PtsRad(polygon[i],polygon[j],rad,c);
                foundCircle = true;
                for(int k=0;k<n && foundCircle;k++)
                    if(dist(polygon[k],c> > 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 & Try With Live Editor

Input

x
+
cmd
3
0 0
1 0
0 1
1.0
3
0 0
1 0
0 1
0.1
0

Output

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

Demonstration


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

Previous
UVA Online Judge solution 10004-Bicoloring UVA online judge solution in C,C++,Java
Next
UVA Online Judge solution - 10020 - Minimal coverage - UVA online judge solution in C,C++,Java