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

NEERC 2009, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Kill the Shaitan-Boss

Time limit: 0.5 second
Memory limit: 64 MB
At the meeting where Maximilian and other members of the program committee were discussing problems for the forthcoming subregional contest, it turned out that the problem set lacked a geometrical problem. The chairman of the program committee asked Maximilian to invent such a problem before September 1.
On the night from August 30 to August 31, Maximilian was sitting in front of his computer trying to pass the final level of the “Kill the Shaitan-Boss” game. Maximilian was attacked by a horde of shaitan-bosses, but he was armed with a shaitan-tube and managed to shoot down almost all the bosses. Only four bosses were left. Maximilian froze them with a spell and was getting ready to kill them when he noticed that only three charges left in his shaitan-tube. “It doesn’t matter,” Maximilian thought. “I will kill two shaitan-bosses by two shots and after that I will reach the straight line passing through the two remaining bosses and kill them both with one shot. The main thing is not to miss.” We must note here that the shaitan-tube shoots from both its ends at once and kills all the shaitan-bosses on the shooting line.
Maximilian aimed at the first shaitan-boss and was ready to press the “fire” button, when suddenly his mobile phone rang. Frightened Maximilian shot in the air, then cursed himself and the person who called him. After that he answered the call.
“Hello, how are you doing? Have you invented a geometrical problem?”
Of course, it was the chairman of the program committee.
“Oh yes, it’s almost ready, there’s very little left to do. I’ll send you the statement tomorrow night.”
“OK, remember that we have a lot to do, we’ll have no time to think later on.”
“Ah,” Maximilian thought switching off. “Such a game lost! Almost all shaitan-bosses have been killed…” But there was still a chance to kill the remaining four bosses with two shots. For that he just needed to carefully calculate his movement and shooting directions. “After I finish the game, I will start thinking about the problem,” Maximilian decided. Of course, he didn't even start inventing the problem. “I only need to shoot down these shaitan-bosses as soon as possible…”


Assume that Maximilian and the shaitan-bosses are points on a plane. Let us introduce a coordinate system and denote the point where Maximilian stands as its origin. Then the i-th shaitan-boss will have coordinates (xi, yi). No three shaitan-bosses stand in the same straight line. Maximilian can stand in the same point with the shaitan-boss and he will kill this boss if he shoots from this point.
The input contains four lines, each containing two space-separated integers xi and yi (|xi|, |yi| ≤ 10000).


Output the minimal distance Maximilian must walk in order to kill all the shaitan-bosses, accurate to 10−5.


-2 0
2 0
-2 4
2 4
Problem Author: Alexander Ipatov
Problem Source: NEERC 2009, Eastern subregional contest
To submit the solution for this problem go to the Problem set: 1719. Kill the Shaitan-Boss