TLE '16 Contest 7 P2 - Judging

View as PDF

Submit solution

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

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 N teams competing today, numbered from 1 to N. The i^\text{th} team is located at (x_i,y_i), in meters from the center of the room. During the contest, there will be T events where a team will notify Mr. C that they want to be judged. On the j^\text{th} event, team t_j notifies Mr. C to travel to their location s_j 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 1 meter per second. As the events occur, he will visit the teams in order of the time they notify him. If, however, team 1 notifies him, he will go to team 1 before going to the other teams, since that team is from his school. He will go to team 1 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 (0,0). 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, N and T (1 \le N,T \le 10^5).

N lines of input follow. The i^\text{th} line will contain two space-separated integers, x_i and y_i (-10^3 \le x_i,y_i \le 10^3). All (x_i,y_i) are pairwise distinct, and no team will be located at (0,0).

T lines of input follow. The j^\text{th} line will contain two space-separated integers, t_j and s_j (0 \le s_j \le 10^9). It is guaranteed that s_j < s_{j+1}.

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 10^{-6}.

Sample Input 1

3 5
2 4
3 0
3 1
2 2
1 4
3 6
2 15
1 16

Sample Output 1


Explanation for Sample Output 1

At 2 seconds, team 2 calls for Mr. C to head over.

After he walks for 2 seconds, team 1 calls for him and he switches direction to go toward team 1 instead. He is located at (2,0) when this occurs.

During his walk to team 1, team 3 calls for him to judge them, but he must first visit teams 1 and 2, in that order.

After finishing the first 3 visits, no team makes a call until 15 seconds, so Mr. C stays put at team 3's location.

When team 1 calls at 16 seconds, Mr. C has already arrived at team 2 from their notification at 15 seconds.

Sample Input 2

3 3
0 50
0 5
0 15
3 0
2 4
1 20

Sample Output 2


Explanation for Sample Output 2

Mr. C must initially walk from his starting position to team 3.

At 4 seconds, team 2 notifies Mr. C, and at 5 seconds, Mr. C reaches team 2's location, but because team 3 notified Mr. C first, he will skip over team 2 to judge team 3 first.

At 20 seconds, Mr. C is returning to team 2 when team 1 notifies him. Mr. C goes all the way to team 1 to judge them before returning back to team 2.


There are no comments at the moment.