|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|3 초||1024 MB||26||6||4||33.333%|
In distant future, humanity found a large, warm and lush planet to colonize, and is building a lot of power plants to support the new colony. The stunning technology allows the builders to harness the vast energy of the Universe. However, there is a small fact they overlooked: building two power plants too close to each other yields a considerable risk of a chain reaction, which would in turn lead to a spectacular explosion. This, obviously, should be avoided.
Fortunately, there are two types of energy that can be used in plants, called light and dark energy, which do not interact with each other. If some of the power plants work on light, and some on dark energy, the distance between identical plants may be larger than before, which would make the whole undertaking less hazardous.
Given the locations of $n$ plants (the planet is big enough so that we can treat them as points on a plane), assign to every plant either light or dark energy so that the Euclidean distance between two same-type plants is maximal possible. To avoid real numbers output, as the answer, the square of this maximal distance, as well as the partition of the plants into "light" and "dark" ones.
In the first line of input there is a single integer $N$ ($3 \leq N \leq 100\,000$) -- the number of power plants.
Of the following $N$ lines, the $i$-th one contains two integers $x_i$, $y_i$ ($0 \leq x_i, y_i \leq 10^9$) -- the coordinates of the $i$-th plant. All points are distinct.
In the first line of output, print a single integer -- the square of the maximal distance which can be achieved. The second line should contain the number of plants working on light energy, the third line -- a space-separated list of these plants' numbers. The fourth and fifth line should describe the dark energy plants, in the same format. If there are multiple valid solutions, output any one of them.
4 0 3 0 0 3 0 3 3
18 2 1 3 2 2 4