Connection Status:
Competition Arena > PolyMove

PolyMove

SRM 304 · 2006-05-27 · by dgoodman

SRM 304 · 2006-05-27 · by dgoodman · Dynamic Programming, Geometry
Class Name: PolyMove
Return Type: double
Method Name: addedArea
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given the vertices of a convex polygon in clockwise order. As you traverse the boundary in the given order, your heading adjusts toward your right at each vertex by more than 0 but less than 180 degrees. As you complete the circuit by going from the last vertex to the first vertex and then heading toward the second vertex, your total heading adjustment has been 360 degrees.

We want to increase the size of the given convex polygon by picking some of its vertices and moving them. We are not allowed to choose vertices that are adjacent to each other, and we are not allowed to move a chosen vertex a distance of more than 1. Of course the boundary segments between a moved vertex and its fixed adjacent vertices also move -- we require that moving boundary segments never intersect any other boundary segments. This guarantees that we will end up with a polygon (possibly not convex) that has a well-defined interior and exterior.

Create a class PolyMove that contains a method addedArea that is given the sequence of vertices of a convex polygon in int[]s x and y. It returns the greatest increase in area that can be achieved by choosing and moving vertices. The coordinates of the i-th vertex are given by the i-th elements of x and y. There is a boundary segment between the last vertex and first vertex.

Notes

  • A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

  • x and y will contain the same number of elements, a number between 3 and 50, inclusive.
  • Each element of x and of y will be between -1000 and 1000, inclusive.
  • The points corresponding to x and y will be distinct.
  • The described polygon will be clockwise convex as specified above.
Examples
0)
{0,1,2}
{0,1,0}
Returns: 1.0

This is an isosceles triangle that has an area of 1. We can increase its area most by moving the middle point from (1,1) to the point (1,2). Now the triangle will have an area of 2, so the increase in area is 1.

1)
{0,1,1,0}
{1,1,0,0}
Returns: 1.4142135623730951

This polygon is a unit square. We can move (0,0) and (1,1), moving them each one unit along the 45 degree diagonal to (-1/sqrt(2),-1/sqrt(2)) and (1+sqrt(2),1+sqrt(2)) respectively. The new polygon is diamond shaped and has an area of 1 + sqrt(2), so its area has increased by sqrt(2).

2)
{0,1,2,3,4,5,6,7,8,9}
{0,9,17,24,30,35,39,42,44,0}
Returns: 44.798129010506386
3)
{0,50,100,150,200,200,0}
{200,202,203,203,202,0,0}
Returns: 296.1807877329639
4)
{0,2,19,30,29}
{0,300,300,1,0}
Returns: 300.7603622931292

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

Coding Area

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

Submitting as anonymous