Connection Status:
Competition Arena > PolygonCover

PolygonCover

SRM 386 · 2008-01-05 · by eleusive

SRM 386 · 2008-01-05 · by eleusive · Dynamic Programming, Geometry, Graph Theory
Class Name: PolygonCover
Return Type: double
Method Name: getArea
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You're given several points in the cartesian plane. Return the smallest possible total sum of areas of a set of convex polygons such that each point is covered by at least one polygon. Moreover, the vertices of each polygon must all lie on the given points, and each polygon must have at least three sides. A point is covered by a polygon if the point lies in the polygon's interior or on its boundary.

The points are described by int[]s x and y, where (x[i],y[i]) is the location of the ith point.

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.
  • A polygon is convex if its edges only intersect at its vertices with each vertex sharing exactly two edges, and it's possible to complete a walk around the polygon by only making left turns.
  • If two polygons with areas A and B overlap, then an area of A+B is contributed to the result.

Constraints

  • x and y will each contain between 3 and 15 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element of x and y will be between -1000 and 1000, inclusive.
  • No three points represented by x and y will lie on a common line.
Examples
0)
{0,10,0,-10}
{-10,0,10,0}
Returns: 200.0

The best way to cover these points is a square that has the four points as vertices.

1)
{-708,-241,-613}
{662,-120,-221}
Returns: 169035.5
2)
{-229,69,15,-70,47,191,-82,140,185,-148,181,109,-77,182,102}
{35,-159,-62,-116,-232,-216,-156,154,-187,143,-57,186,-17,-136,-7}
Returns: 1800.5
3)
{117,36,-55,177,-51,-69,178,19,-106}
{-162,-41,25,-193,-202,-184,212,8,-10}
Returns: 3780.0
4)
{-1,2,-2,0}
{-1,0,2,-1}
Returns: 2.0

The optimal solution here is to use two triangles; one triangle has vertices at points 0, 1, and 3 while the other triangle has vertices at points 0, 2, and 3.

Submissions are judged against all 141 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PolygonCover with a public method double getArea(vector<int> x, vector<int> y) · 141 test cases · 2 s / 256 MB per case

Submitting as anonymous