DMPG '15 G4 - Spacetime Convergence Cannons

View as PDF

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Embryo is about to be defeated. All that's left to do is to launch 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 another corner at . 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 and . 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 and .

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 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 and , separated by a single space.

The next lines contain the integer coordinates of the spacetime convergence cannons, in pairs. No two cannons will be at the same location and and

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

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

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

5

Explanation of Output for Sample Input

The second cannon is hit by the fourth cannon, so its disadvantage is .

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