Special Relativity

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

James "Chad" Su was drifting through an intersection when he was T-boned by a Tesla Roadster travelling at a significant fraction of the speed of light.

James and the Tesla driver disagree on when the street light opposite the Tesla turned green and are having trouble settling the dispute.

James isn't a fan of Einstein's shenanigans or getting his car wrecked, so he decides to try and get light speed Teslas banned from driving on city roads. In order to provide evidence for how problematic these vehicles are, he wants to know the sum of the differences in observed time at all points where such discrepancies can occur.

The city consists of N street lights and M drivers. The i^\text{th} street light's location is represented by the point (x_i, y_i). In James's universe, light travels at C units per second. At the instant captured by the problem input, every street light's colour has simultaneously changed relative to the plane.

The v^\text{th} driver is represented by a position vector [p_{x,v}, p_{y,v}] and a direction vector [d_{x,v}, d_{y,v}]. Initially, the drivers are located at their position vector's coordinates - the point (p_{x,v}, p_{y,v}). Every second, their location is moved by the direction vector (i.e., (x, y) \to (x+d_x, y+d_y)).

The time at which a driver has seen a street light change colour is defined as the time at which the driver receives the first ray of new colour light from the street light.

Find the sum of the absolute time differences in between the times that every pair of drivers experiences every light change colour.

For this problem, Python users are recommended to use PyPy over CPython.

Note that an understanding of special relativity is not required to solve this problem.


1 \le N, M \le 4 \cdot 10^3

-10^9 \le x_i, y_i, p_{x,v}, p_{y,v}, d_{x,v}, d_{y,v} \le 10^9

2 \le C \le 10^9

\sqrt{d_{x,i}^2+d_{y,i}^2} \le \frac{C}{2}

Assume that all measurements of length, position, and time are taken relative to the plane.

Subtask 1 [10%]

N, M \le 300

-10 \le x_i, y_i, p_{x,v}, p_{y,v}, d_{x,v}, d_{y,v} \le 10

C \le 100

Subtask 2 [10%]

N, M \le 300

Subtask 3 [40%]

N, M \le 10^3

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line of input contains 3 integers N, M, and C - the number of street lights, number of drivers, and the speed of light, respectively.

The next N lines contain 2 integers x_i and y_i - the x and y coordinates of the i^\text{th} streetlight, respectively.

The next M lines contain 4 integers p_{x,v}, p_{y,v}, d_{x,v}, and d_{y,v} - the v^\text{th} driver's initial position vector's x and y components, and the v^\text{th} driver's direction vector's x and y components, respectively.

Output Specification

Output a single line with a single number - the sum of the absolute time differences in between the times that every pair of drivers experiences every light change colour.

More specifically, the value of the following expression:

\displaystyle \sum_{a=1}^{M-1} \sum_{b=a+1}^M \sum_{i=1}^N \left|T_{a,i}-T_{b,i}\right|

Where T_{v,i} is the time at which the v^\text{th} driver experiences the i^\text{th} light change colour.

Output the result of the expression. If the correct answer is B, the grader will view A as correct if |A-B| \le 10^{-5} or \frac{|A-B|}{B} \le 10^{-5}.

Sample Input 1

1 2 15
0 0
-5 2 0 -6
-2 -10 -6 3

Sample Output 1


Sample Explanation 1

The following GIF shows the first second of the motion, in which both observers witness the light change colour. The first observer to see the light views it at time \frac{1}{3}, while the second views it at time \frac{2}{3}, for a total time difference of \frac{1}{3}. Note that any real number from 0.33332\bar{3} to 0.33334\bar{3} would have been accepted.


  • 4
    Plasmatic  commented on Sept. 1, 2021, 9:40 p.m. edit 3

    The constraints of this problem were updated post contest. Be careful if you are upsolving.

    More specifically:

    \displaystyle N: 2\,000 \rightarrow 4\,000