Under construction

Still being built. Things may change

Aliens

Interview

Time limit1sMemory limit128 MB

Summary
Given N points, choose an integer axis value s minimizing new points needed so the set is symmetric about x = s/2, then output those points. Ties go to the smallest s, output sorted by x then y.
Level

Medium6 of 10

Topics
Hash map, Sorting, Implementation, Geometry
Solved
No attempts yet

Problem

To make contact with aliens, huge structures visible from space were built across the Earth. After 15 years and ten quadrillion kuna, a team of scientists concluded that showing there is intelligent life on Earth calls for symmetry in how the structures are placed. The first step of the plan is to make the layout symmetric about a line parallel to the yy axis of the Cartesian coordinate system that holds the structure locations.

For a real number cc, the layout is symmetric about the line x=cx = c when every occupied coordinate (x,y)(x, y) has a structure at (2c−x,y)(2c - x, y) as well.

The budget ran out long ago, so the symmetry has to be reached while building as few new structures as possible. Find the smallest number of new structures and their locations.

Input

The first line contains the number of existing structures NN. (1≤N≤10001 \le N \le 1000)

Each of the next NN lines contains two integers XX and YY, the coordinates of one structure. Both values are smaller than 10810^8 in absolute value. No two structures share the same coordinates.

Output

On the first line, print the smallest number RR of new structures.

On each of the next RR lines, print the coordinates of one new structure.

Several answers can reach the minimum, so pick one by the following rule. A new structure also has integer coordinates, so s=2cs = 2c is an integer for the axis x=cx = c. If more than one ss reaches the smallest RR, take the smallest such ss. For that axis, print the new coordinates in increasing order of xx, breaking ties by increasing yy.

Examples3

  1. Example 1

    Input
    3
    1 5
    3 2
    6 5
    
    Expected output
    1
    4 2
    
  2. Example 2

    Input
    7
    1 3
    3 2
    4 4
    7 2
    8 4
    11 3
    10 4
    
    Expected output
    3
    2 4
    5 2
    9 2
    
  3. Example 3

    Input
    4
    2 3
    7 3
    4 3
    6 3
    
    Expected output
    1
    1 3