26188번 - Constellations 다국어

문제

Astrologists took a hard scientific look at their zodiac horoscope predictions and realised that their methodology doesn't provide future insight better than chance. Instead of looking inwards they blame the stars and historical construction of constellations for their inability to predict the future. They're testing out a new way of constructing constellations that will renew their powers of future-sight.

They need your help to implement their iterative constellation creation system. Initially every star represents its own constellation. In every step you should merge two constellations into one, by picking the constellations that are closest to each other. The distance between two constellations $A$ and $B$ is defined as the average squared Euclidean distance of pairs of stars from each constellation:

$$ d(A, B) = \frac{1}{|A||B|}\sum_{a\in A}\sum_{b\in B}||a-b||^2.$$

If multiple pairs have the same distance you should merge older constellations first. When comparing two pairs of constellations that could be merged, first compare the distances between constellations. If both pairs are at exactly the same distance, compare them by the age of the older constellation in a pair. If there is still a tie, compare them by the age of the newer constellation in a pair. A constellation's age is defined by the time when it was formed with the last merge, or in case of single-star constellations by the age of the star. The stars in the input are listed from oldest to youngest.

입력

The first line contains $N,ドル the number of stars. The next $N$ lines contain coordinates of stars with two space-separated integers $X_i$ and $Y_i$.

출력

After every step of the described constellation creation system, print out the size of the newly created constellation. You should output $N-1$ lines.

제한

• 2ドル \leq N \leq 2000$
• $-1000 \leq X_i, Y_i \leq 1000$ for all 1ドル \leq i \leq N$
• All pairs $X_i,ドル $Y_i$ are unique since it's physically impossible for two stars to lie on the same point.

힌트