
Mr. C is a judge at the ECOO (Educational Cooking Organization of Ontario) contest. The ECOO contest involves teams of students correctly preparing as many dishes as possible. Dishes must be evaluated by a judge in order to count.
There are teams competing today, numbered from
to
. The
team is located at
, in meters from the center of the room. During the contest, there will be
events where a team will notify Mr. C that they want to be judged. On the
event, team
notifies Mr. C to travel to their location
seconds after the start of the contest. It is guaranteed that no team will make more than one notification before Mr. C visits them and that at any second, at most one event occurs.
Mr. C can only walk at a speed of meter per second. As the events occur, he will visit the teams in order of the time they notify him. If, however, team
notifies him, he will go to team
before going to the other teams, since that team is from his school. He will go to team
even if he is in the middle of traveling to another team.
Mr. C does not know the events ahead of time and he will travel a straight-line distance from his current location to his destination. If he happens to pass by a team that is not his next destination, he will not judge that team, effectively skipping over the team to judge at a later time. If at anytime no team is calling him, he will remain at his current location.
Mr. C starts at . After satisfying all of the notifications, he remains where he is. He wants to know the total distance he walks throughout the contest so he can tell if he exercised enough after eating the teams' dishes. Can you help him?
Input Specification
The first line of input will contain two space-separated integers, and
.
lines of input follow. The
line will contain two space-separated integers,
and
. All
are pairwise distinct, and no team will be located at
.
lines of input follow. The
line will contain two space-separated integers,
and
. It is guaranteed that
.
Output Specification
Output the total distance that Mr. C will walk throughout the contest. Your answer will be judged as correct if its absolute or relative error does not exceed .
Sample Input 1
3 5
2 4
3 0
3 1
2 2
1 4
3 6
2 15
1 16
Sample Output 1
16.246211
Explanation for Sample Output 1
At seconds, team
calls for Mr. C to head over.
After he walks for seconds, team
calls for him and he switches direction to go toward team
instead. He is located at
when this occurs.
During his walk to team , team
calls for him to judge them, but he must first visit teams
and
, in that order.
After finishing the first visits, no team makes a call until
seconds, so Mr. C stays put at team
's location.
When team calls at
seconds, Mr. C has already arrived at team
from their notification at
seconds.
Sample Input 2
3 3
0 50
0 5
0 15
3 0
2 4
1 20
Sample Output 2
105.000000
Explanation for Sample Output 2
Mr. C must initially walk from his starting position to team .
At seconds, team
notifies Mr. C, and at
seconds, Mr. C reaches team
's location, but because team
notified Mr. C first, he will skip over team
to judge team
first.
At seconds, Mr. C is returning to team
when team
notifies him. Mr. C goes all the way to team
to judge them before returning back to team
.
Comments