Under construction

Still being built. Things may change

Polygon Programming with Ease

Interview

Time limit1sMemory limit128 MB

Summary
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 NN Foreign Offices located at distinct points in the plane, placed in order as the vertices of a polygon: F1,F2,…,FNF_1, F_2, \dots, F_N. On each edge joining two neighbouring Foreign Offices, a single meeting location is placed at the midpoint of that edge. That is, for i=1,2,…,N−1i = 1, 2, \dots, N-1 the meeting location MiM_i is the midpoint of FiF_i and Fi+1F_{i+1}, and MNM_N is the midpoint of FNF_N and F1F_1.

Given the coordinates of the NN meeting locations M1,M2,…,MNM_1, M_2, \dots, M_N in that order, determine the coordinates of the NN Foreign Offices F1,F2,…,FNF_1, F_2, \dots, F_N. When NN 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 NN (3≤N3 \le N), followed by 2N2N integers x1 y1 x2 y2 … xN yNx_1\ y_1\ x_2\ y_2\ \dots\ x_N\ y_N, where (xi,yi)(x_i, y_i) is the coordinate of the ii-th meeting location MiM_i, listed in order around the polygon. All coordinates are integers.

Output

For each test case, print one line. First print the integer NN, then the coordinates of the Foreign Offices F1,F2,…,FNF_1, F_2, \dots, F_N 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 ii-th meeting location is the midpoint of the ii-th and (i+1)(i+1)-th Foreign Office (indices are cyclic, so MNM_N is the midpoint of FNF_N and F1F_1). Because NN is odd, the Foreign Offices can be recovered uniquely: first take the alternating sum F1=M1−M2+M3−⋯+MNF_1 = M_1 - M_2 + M_3 - \dots + M_N, then compute the rest with Fi+1=2Mi−FiF_{i+1} = 2M_i - F_i for i=1,2,…,N−1i = 1, 2, \dots, N-1.

Examples2

  1. Example 1

    Input
    5 14 2 20 4 18 12 12 18 10 10
    3 -3 5 -2 5 -3 6
    3 -2 10 5 10 -1 12
    
    Expected output
    5 10.000000 2.000000 18.000000 2.000000 22.000000 6.000000 14.000000 18.000000 10.000000 18.000000
    3 -4.000000 6.000000 -2.000000 4.000000 -2.000000 6.000000
    3 -8.000000 12.000000 4.000000 8.000000 6.000000 12.000000
    
  2. Example 2

    Input
    3 2 1 2 3 0 2
    
    Expected output
    3 0.000000 0.000000 4.000000 2.000000 0.000000 4.000000