ICPC 2024 · Problem F · Friendly Rivalry

Time limit: 2 seconds

The leaders of the International Coalition for Planetary Change (ICPC), a non-profit fighting for envi- ronmental awareness, are worried that their regional chapters are not doing enough to make a real impact on climate change. Inspired by the latest studies that competition is one of the best motivators, they have decided to start a competition between their chapters.

At the same time, the ICPC does not want to slow the spread of ideas. To encourage chapters to share effective climate change methods, the ICPC has decided to assign their $2n$ chapters into two teams, the green team and the blue team. For balance, each team should consist of exactly $n$ chapters.

To ensure the teams are not getting in each other’s way, the ICPC wants the two teams to be as far apart as possible. Specifically, the Euclidean distance between the closest pair of chapters belonging to different teams should be as large as possible.

Help the ICPC set up the teams according to these rules.

Input

The first line contains an integer $n$ ($1 \le n \le 500$), the size of each team. Chapters are numbered from $1$ to $2n$. Each of the remaining $2n$ lines contains two integers $x_{i}$ and $y_{i}$ ($- 10 ^{9}\le xi, yi \le 10^{9}$), the Cartesian coordinates of the location of the $i$th chapter. All chapters are at distinct locations.

Output

Output $n+ 1$ numbers. The first number is the distance between the two closest chapters belonging to different teams. The next $n$ numbers are the chapters belonging to the blue team. If there are multiple ways to divide the teams with the same minimal distance, output any of them. The distance should have an absolute or relative error of at most $10^{- 6}$.

Sample Input 1

2
0 1
1 0
1 1
0 0

Sample Output 1

1.000000
1
2

Sample Input 2

2
0 1
-1 -1
1 0
2 2

Sample Output 2

2.236068
4
2

Sample Input 3

3
0 0
1 1
2 2
3 3
4 4
5 5

Sample Output 3

1.414214
1
2
3