HackerRank : Week of Code 23 – Enclosure

By | September 17, 2016

Vigo the Carpathian is an evil feudal lord. He wants to seize land from his serfs by enclosing it with a polygonal fence where each respective side has a strictly specified length. Can you help him maximize the fenced area?

Given a sequence of lengths (i.e., ) where each is the length of the side, find a sequence of points (where ) such that and where is the Euclidean distance between points and . Note that the first point, , must be and the second point, , must be . These points must correspond to the ordered clockwise vertices of the simple polygon having the maximum possible area for the given side lengths. Then print the points according to the instructions in the Output Format section below.

Input Format (Enclosure)

The first line contains a single integer, , denoting the number of sides in the polygon.
The second line contains space-separated positive integers describing each respective . It is guaranteed that you can form an -edge polygon with the given sequence of lengths.

Constraints

Output Format (Enclosure)

For each of the points (i.e., vertices in the polygon), print three lines in the following format:

  1. The first line must contain a single floating-point number denoting the point’s -coordinate.
  2. The second line must contain a single floating-point number denoting the point’s -coordinate.
  3. The third line must be empty and serves as a visual spacer between the last point’s -coordinate and the next point’s -coordinate.

You must print a total of lines of output. Your output is considered to be correct if the absolute difference from the correct answer for each coordinate is not greater than . It is guaranteed that the exact correct answer is unique.

Sample Input 0

4
1 2 1 2

Sample Output 0

0.000000
0.000000

0.000000
1.000000

2.000000
1.000000

2.000000
0.000000

Explanation 0
The enclosure is a quadrilateral (specifically, a parallellogram). The area enclosed by the fence is maximal when it’s a rectangle.

Sample Input 1

3
1 1 1

Sample Output 1

0.000000
0.000000

0.000000
1.000000

0.866025
0.500000

Explanation 1
The only possible polygon is an equilateral triangle.