Problemas
The leaders of the International Coalition for Planetary Change (ICPC), a non-profit fighting for environmental 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 2𝑛 chapters into two teams, the green team and the blue team. For balance, each team should consist of exactly 𝑛 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.
Entrada
The first line contains an integer 𝑛 (1≤𝑛≤500), the size of each team. Chapters are numbered from 1 to 2𝑛. Each of the remaining 2𝑛 lines contains two integers
Salida
Output 𝑛+1 numbers. The first number is the distance between the two closest chapters belonging to different teams. The next 𝑛 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
Ejemplo #1
2
0 1
1 0
1 1
0 0
1.000000
1
2
Ejemplo #2
2
0 1
-1 -1
1 0
2 2
2.236068
4
2
Ejemplo #3
3
0 0
1 1
2 2
3 3
4 4
5 5
1.414214
1
2
3
Debes iniciar sesión para escribir código.