## TLE '16 Contest 7 P2 - Judging

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Students having fun at last year's ECOO contest!

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 .