Bovine Bridge Battle
InterviewTime limit1sMemory limit128 MB
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 cows () is waiting in the main pasture, with cow standing at the integer coordinates ().
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 in the plane (not coincident with any of the four cows' positions) such that rotating each cow of the group about 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 . 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: (rotating about ), (about ), and (about ).
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 .
- Lines 2 to : Line contains two space-separated integers and .
Output
- Line 1: A single integer — the number of sets of four cows that can form a valid Bridge group.