Polygon Programming with Ease
InterviewTime limit1sMemory limit128 MB
Given the midpoints of the edges of a polygon with an odd number of vertices, recover the original vertex coordinates using an alternating sum and forward substitution.
- Level
Easy3 of 10
- Topics
- Math, Geometry, Implementation, Array
- Solved
- No attempts yet
Problem
There are Foreign Offices located at distinct points in the plane, placed in order as the vertices of a polygon: . On each edge joining two neighbouring Foreign Offices, a single meeting location is placed at the midpoint of that edge. That is, for the meeting location is the midpoint of and , and is the midpoint of and .
Given the coordinates of the meeting locations in that order, determine the coordinates of the Foreign Offices . When is odd the Foreign Offices are uniquely determined.
Input
The input consists of several test cases and is processed until end of file. Each test case is given on a single line. It starts with an odd integer (), followed by integers , where is the coordinate of the -th meeting location , listed in order around the polygon. All coordinates are integers.
Output
For each test case, print one line. First print the integer , then the coordinates of the Foreign Offices in the same order as the meeting locations. Print every coordinate with exactly six digits after the decimal point, and separate all values with single spaces.
Hint
The -th meeting location is the midpoint of the -th and -th Foreign Office (indices are cyclic, so is the midpoint of and ). Because is odd, the Foreign Offices can be recovered uniquely: first take the alternating sum , then compute the rest with for .