Bovine Bridge Battle

Interview

Time limit1sMemory limit128 MB

Summary
Count sets of four points that are symmetric about some center, where each point pairs with its 180-degree rotation partner.
Level

Medium5 of 10

Topics
Hash map, Geometry, Combinatorics, Math
Solved
No attempts yet

Problem

Each of Farmer John's NN cows (4≤N≤10004 \le N \le 1000) is waiting in the main pasture, with cow ii standing at the integer coordinates (Xi,Yi)(X_i, Y_i) (−109≤Xi,Yi≤109-10^9 \le X_i, Y_i \le 10^9).

The cows want to form groups of four to play Bridge, their new favorite card game. Each group must satisfy the following constraint: four cows may team up if and only if there exists some point PP in the plane (not coincident with any of the four cows' positions) such that rotating each cow of the group 180∘180^\circ about PP lands exactly on the position of another cow in the same group.

In other words, the four positions must be point-symmetric about some center PP. Determine how many sets of four cows can form a Bridge group.

For example, suppose eight cows stand at the following eight points.

                  |
                 f*
                  |             a = (-3, 1)    e = (-1, 1)
           b*     |             b = (-2, 2)    f = ( 0, 3)
        a      e  |             c = (-3, 0)    g = ( 2, 0)
         *     *  |             d = (-2, 0)    h = ( 3, 0)
         c  d     |     g  h
---------*--*-----+-----*--*---------
                  |

Then there are exactly three legal groups: {a,b,e,d}\{a, b, e, d\} (rotating about (−2,1)(-2, 1)), {b,c,e,f}\{b, c, e, f\} (about (−1.5,1.5)(-1.5, 1.5)), and {c,d,g,h}\{c, d, g, h\} (about (0,0)(0, 0)).

All given cow positions are distinct and are provided in no particular order. The answer is guaranteed to fit in a signed 32-bit integer.

Input

  • Line 1: A single integer NN.
  • Lines 2 to N+1N+1: Line i+1i+1 contains two space-separated integers XiX_i and YiY_i.

Output

  • Line 1: A single integer — the number of sets of four cows that can form a valid Bridge group.

Examples3

  1. Example 1

    Input
    8
    -3 0
    -2 0
    -1 1
    0 3
    2 0
    -3 1
    3 0
    -2 2
    
    Expected output
    3
    
  2. Example 2

    Input
    4
    0 0
    2 0
    0 2
    2 2
    
    Expected output
    1
    
  3. Example 3

    Input
    4
    0 0
    1 0
    0 1
    5 5
    
    Expected output
    0