(Computational?) Geometry problems from POJ

Here's a short list of some mixed geometry flavored problems from POJ.

1039	1066	1113	1151	1177	1228	1254	1263	1269	1385	1389	1408	1410
1556	1584	1696	1765	1819	1837	1873	2031	2043	2074	2079	2165	2187
2242	2280	2318	2354	2398	2420	2423	2540	2653	2826	2954	2966	3004
3130	3227	3277	3304	3335	3347	3348	3384	3429	3449	3525	3608	3695

There is a possibility that some of these may not be geometry problem at all, tried my best to sort them out though. Also, some of these problems are not solvable by only geometry knowledge. Graph, dynamic programming, and understanding of advanced data structure may also be required.

Convex Hull

In computational geometry, Convex Hull or Convex Polygon is a very common term and we face many problems which require the construction of a Convex Hull to generate desired solution.

A convex hull is a convex polygon which has the minimal area to contain the set of given points. In other words, for a given set of points, a Convex Hull is such a Convex Polygon that, every point on the set is either on the Polygon or inside the Polygon.

So, a typical problem might ask, "You are given n integer co-ordinates (3 ≤ n ≤ 10⁵), find the Convex Hull". It means it wants you to write down the co-ordinates of the picks or, find the convex area, or, find the center of gravity of it, or, sometimes, you are asked to create an arbitrary convex hull, or you may be asked, find whether a given point is inside a convex hull, and so on... Well, before getting into the harder ones, lets see how we can construct a convex hull smartly :P

There are a number of ways to compute convex hull from the given points. Like, I found those in wikipedia, (I know only three of them):

• Direct method
• Gift Wrapping (Packaging) method
• Graham's scan method
• Incremental (Sequential addition) method
• Divide and Conquer method
• Quick method (related to Quick Sort)
• Inner point elimination

The graham scan method is the most widely used method that has a complexity of O( n lg n ) for n points. In this method, the algorithm starts from a extreme (topmost / leftmost / rightmost / bottommost) point and keep wrapping all the other points unless it reaches the beginning point. Here's a little animation that shows it:


For detailed reading, you can visit Wikipedia or read Introduction to Algorithm - CLRS. Here's my implementation for finding Convex Hull with the help of Graham Scan method (integer points only):

#include <algorithm>
using namespace std;

#define MAX 100009
#define i64 long long
#define sq(x) ((x)*(x))

struct point {
    i64 x, y;
} P[MAX], C[MAX], P0;

// P[] contains all points
// C[] contains convex hull ccw

inline i64 TriArea2(point a, point b, point c) {
    return (a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y));
}

inline i64 sqDist(point a, point b) {
    return (sq(a.x-b.x) + sq(a.y-b.y));
}

bool comp(point a, point b) {
    i64 d = TriArea2(P0, a, b);
    if(d<0) return false;
    if(!d && sqDist(P0, b) > sqDist(P0, a)) return false;
    return true;
}

void ConvexHull(int np, int &nc) {
    int i, j, pos = 0;
    for(i=1; i<np; i++)
        if(P[i].y<P[pos].y || (P[i].y==P[pos].y && P[i].x>P[pos].x))
            pos = i;
    swap(P[0], P[pos]);
    P0 = P[0];
    sort(&P[1], P+np, comp);
    C[0] = P[0], C[1] = P[1], C[2] = P[2];
    for(i=j=3; i<np; i++) {
        while(TriArea2(C[j-2], C[j-1], P[i]) <= 0) j--;
        C[j++] = P[i];
    }
    nc = j;
}

Here,
TriArea2() returns the double of triangular area formed by the three points passed as its argument.
sqDist() returns the square distance between two points passed as its argument.
sort() is stl sort that sorts the P[] array according to their slope.
The first loop in ConvexHull() finds the starting point, i.e. the bottommost and rightmost point. After sorting rest of the points correctly, the second loop examines which point is to be added to the Hull. Finally nc is the number of points in convex hull updated via reference. There is no checking for n < 3 or if there are duplicates (actually if number of distinct points are ≥ 3, it doesn't matter in this method), we need to handle that according to problem requirement.

Not much tough as it seems to be ... happy coding

Segment-Circle Intersection

This is a sample code which verifies whether a given Circle and Segment intersects or not.

/*
**  Verifies the intersection of a segment and a circle
**  The line segment is defined from points p1 to p2
**  The circle is of radius r and centered at point c
**  There are potentially two points of intersection given by
**  p = p1 + mu1 (p2 - p1)
**  p = p1 + mu2 (p2 - p1)
**  mu1 and mu2 are updated via reference
**  Return FALSE if the segment doesn't intersect the circle
*/
bool cross(POINT p1, POINT p2, CIRCLE p, double &mu1, double &mu2) {
    double a, b, c, d;
    POINT t;
    t.x = p2.x - p1.x;
    t.y = p2.y - p1.y;
    a = sq(t.x) + sq(t.y);
    b = 2.0 * (t.x * (p1.x - p.c.x) + t.y * (p1.y - p.c.y));
    c = sq(p.c.x) + sq(p.c.y);
    c += sq(p1.x) + sq(p1.y);
    c -= 2.0 * (p.c.x * p1.x + p.c.y * p1.y);
    c -= sq(p.r);
    d = b * b - 4 * a * c;
    if(fabs(a) < eps || d < -eps) {
        mu1 = mu2 = 0.0;
        return false;
    }
    mu1 = (-b + sqrt(d)) / (2.0 * a);
    mu2 = (-b - sqrt(d)) / (2.0 * a);
    return true;
}