137 - Polygons

Compute the intersection of two convex hulls.

My solution to this problem is not very elegant: For all pairs of segments of the two convex hulls, it computes the intersecting point of the two segments. Then it computes the convex hull of the intersecting points and “inner” points as the intersection of the input convex hulls.

Note: At first, I implemented a Rational class, but later I realized that there were many potential integer overflow bugs when input data were complex, especially when computing the area of the intersecting convex hull; so I switched to double.