Under construction

Still being built. Things may change

You Never Learned Geometry and Vectors?

Interview

Time limit2sMemory limit1024 MB

Summary
Count the pairs of 2D integer vectors whose dot product is zero, where a zero vector counts as perpendicular to every other vector.
Level

Medium5 of 10

Topics
Hash map, Math
Solved
No attempts yet

Problem

Minwoo is a student who entered in 2022. When the 2022 CSAT math exam introduced elective subjects, Minwoo chose Calculus and never learned the beauty of geometry and vectors. Having taught himself geometry and vectors, he wants to show their beauty through the 2023 APC.

The dot product of two vectors v1=(x1,y1)v_{1}=\left( x_{1},y_{1} \right) and v2=(x2,y2)v_{2}=\left( x_{2},y_{2} \right) in the 2D plane is defined as follows.

v1⋅v2=x1x2+y1y2v_{1}\cdot v_{2}=x_{1}x_{2}+y_{1}y_{2}

If the dot product of two vectors is 00, the two vectors are perpendicular on the 2D plane.

Given NN two-dimensional vectors, count the number of ordered pairs (i,j)(i,j) where 1≤i<j≤N1\leq i<j\leq N and vectors viv_{i} and vjv_{j} are perpendicular.

Input

The first line contains NN. (1≤N≤2000001\leq N\leq 200000)

From the second line onward, the next NN lines each contain xix_{i} and yiy_{i}, separated by a space, for vector vi=(xi,yi)v_{i}=(x_{i},y_{i}). (−109≤xi,yi≤109-10^{9}\leq x_{i},y_{i}\leq 10^{9})

All values in the input are integers.

Output

For integers ii and jj satisfying 1≤i<j≤N1\leq i<j\leq N, print the number of ordered pairs (i,j)(i,j) where vectors viv_{i} and vjv_{j} are perpendicular to each other.

Examples1

  1. Example 1

    Input
    9
    1 2
    3 5
    3 6
    2 -1
    -4 2
    4 -2
    -5 0
    -8 -16
    0 3
    
    Expected output
    10