DMPG '15 G4 - Spacetime Convergence Cannons

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem types

Embryo is about to be defeated. All that's left to do is to launch N spacetime convergence cannons at his base of operations. From an aerial view, we can view the spacetime convergence cannons and Embryo's base as objects on the 2D Cartesian plane. Embryo's base is very wide, and is infinitely long. The front face of the base is on a segment of the x-axis, with one corner touching the origin and the other corner at (X, 0). The spacetime convergence cannons are points on a plane, and the beam they shoot hits everything within two rays extending from the cannon which intersect Embryo's base at the corners (0, 0) and (X, 0). See Figure 1 for a better understanding.

Figure 1: The points are spacetime convergence cannons, and the shaded area is where their beams strike.
Note that all beams just barely touch both corners of the base at (0, 0) and (X, 0).

Unfortunately, the large amount of spacetime convergence cannons means that some friendly fire is inevitable. The disadvantage for a single spacetime convergence cannon is the square of the number of other friendly spacetime convergence cannons that hit it. The disadvantage of the entire operation is the sum of the disadvantage values for each individual spacetime convergence cannon. Given X and the locations of the spacetime convergence cannons, please compute the total disadvantage of the operation.

Input Specification

The first line of input contains two integers N and X (1 \le X \le 10^4), separated by a single space.

The next N lines contain the integer coordinates of the spacetime convergence cannons, in x, y pairs. No two cannons will be at the same location and 0 \le x \le X and 1 \le y \le 10^4.


For all subtasks:

1 \le N \le 200\,000

Subtask 1 [5%]

All x-coordinates of the cannons will be the same.

Subtask 2 [5%]

All y-coordinates of the cannons will be the same.

Subtask 3 [5%]

N = 2

Subtask 4 [15%]

1 \le N \le 1\,000

Subtask 5 [70%]

No additional constraints.

Output Specification

Output the total disadvantage on one line.

Sample Input

5 10
1 1
3 2
5 1
6 4
10 1

Sample Output


Explanation of Output for Sample Input

The second cannon is hit by the fourth cannon, so its disadvantage is 1^2 = 1.

The third cannon is hit by both the second and fourth cannons, so its disadvantage is 2^2 = 4.

The total disadvantage is 1+4 = 5.

A diagram of this case is given in the problem statement.


There are no comments at the moment.