Aliens
InterviewTime limit1sMemory limit128 MB
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 axis of the Cartesian coordinate system that holds the structure locations.
For a real number , the layout is symmetric about the line when every occupied coordinate has a structure at 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 . ()
Each of the next lines contains two integers and , the coordinates of one structure. Both values are smaller than in absolute value. No two structures share the same coordinates.
Output
On the first line, print the smallest number of new structures.
On each of the next 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 is an integer for the axis . If more than one reaches the smallest , take the smallest such . For that axis, print the new coordinates in increasing order of , breaking ties by increasing .