This page is still under construction.

Parts of this page are still being built. What you see may change.

Playing with a Divider

Time limit2sMemory limit1024 MB

Summary
Given up to 1000 grid points hit by a divider with fixed needle distance, find all distances such that every point can be paired with another point exactly that far away.
Level

Medium6 of 10

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

Problem

Dima found a special drafting tool on his father's desk, one that looks like a compass: a divider. A divider differs from an ordinary compass in that both of its legs end in needles, while an ordinary compass has a needle on one leg and a pencil lead on the other.

Dima took a sheet of graph paper, set some distance between the needles of the divider and fixed it firmly, and started poking the divider into the sheet of paper. Each time, Dima poked both needles of the divider into the sheet, and he always did so in such a way that the holes landed on the intersection points of the lines that divide the sheet into cells. Dima could insert the divider into the same hole several times.

In the evening, Dima's father found the sheet his son had been playing with and decided to find out what distance between the needles of the divider Dima could have set. All the father knows is the coordinates of the holes made by the needles of the divider. Help the father solve this problem.

Input

The first line of the input file contains the number nn, the number of holes (2≤n≤10002 \le n \le 1000). The following nn lines contain two integers each, the coordinates of the holes. The coordinates do not exceed 10410^4 in absolute value.

Output

On the first line of the output file, print kk, the number of distinct distances Dima could have set between the needles of the divider. The following kk lines must contain one real number each: the distances in question. The distances must be printed in increasing order. Each number must be printed with an accuracy of at least 10−910^{-9}.

It is guaranteed that there is at least one distance Dima could have set between the needles of the divider.

Examples1

  1. Example 1

    Input
    4
    0 0
    1 1
    1 0
    0 1
    
    Expected output
    2
    1.0
    1.414213562373