ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Timus Top Coders: Third Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. National Park

Time limit: 1.0 second
Memory limit: 64 MB


Sergey Flayer, a mayor of Tmutarakan, likes two things: animals and hunting. Once at a session of the City Council he claimed, that the voters lacked very much for some zone, where city chiefs may hunt in comfort conditions. The deputies considered the voters' opinion and issued an edict about an establishment of the National Park of Tmutarakan at the territory of local forest. A duty to draw the border of the future Park was imposed on the Government Committee of Nature Management, which in its turn delegated it to the City Forestry in the person of ranger Kuzmitch.


Kuzmitch equipped with a barbwire reel and went into the forest. On arrival he revealed, that there were N trees in the forest numbered from 1 to N, and calculated their cartesian coordinates (Xi, Yi).
Kuzmitch knew, that the easiest way was to connect any three trees (with different numbers, of course) with barbwire segments, and the triangle they formed would be the border of the National Park. But he also knew, that the barbwire was rather expensive. So Kuzmitch decided to choose these three trees so that the perimeter of the Park would be minimal.


The first line contains the integer number N (3 ≤ N ≤ 50000). Each of the next N lines contains the integer numbers Xi and Yi (-106Xi, Yi ≤ 106) for the corresponding tree.


The first line should contain the minimal perimeter of the National Park printed with at least four digits after decimal point. The second line should contain the numbers of three trees, which should be connected with barbwire. The numbers may be listed in any order and should be separated by single spaces. If the problem has several solutions, you should output any of them.


0 0
1 1
3 0
0 3
3 3
1 2 3


Strange things happen in Tmutarakan forest—the coordinates of some trees may coincide with each other, and a triangle of zero area is considered as a triangle nevertheless.
Problem Author: Nikita Rybak, Ilya Grebnov, Dmitry Kovalioff
Problem Source: Timus Top Coders: Third Challenge
To submit the solution for this problem go to the Problem set: 1514. National Park