#P5286. Counting Fishes

    ID: 18519 Type: Default 1000ms 256MiB

Counting Fishes

Counting Fishes

Given n distinct integer points in the plane, an ordered 6-tuple of points \((A, B, C, D, E, F)\) is called a fish if and only if the following conditions hold:

  • Symmetry constraints: $$AB = AC,\quad BD = CD,\quad DE = DF.$$
  • For the "body" of the fish, the angles $$\angle BAD,\; \angle BDA,\; \angle CAD,\; \angle CDA$$ are all acute (i.e. strictly less than \(90^\circ\)).
  • For the fish tail, the angles $$\angle ADE,\; \angle ADF$$ are greater than \(90^\circ\) (that is, they are obtuse or straight).

Note that even if the same 6 points are chosen, different orders are considered distinct fishes as long as the above conditions are satisfied. For example, \((A, B, C, D, E, F)\) and \((A, C, B, D, E, F)\) are regarded as two different fishes.

Your task is to count how many fishes can be formed from the given points.

inputFormat

The first line contains a single integer \(n\) indicating the number of points. Each of the following \(n\) lines contains two space-separated integers representing the x and y coordinates of a point.

outputFormat

Output a single integer representing the number of fishes (ordered 6-tuples) that can be formed which satisfy the given conditions.

sample

6
0 0
1 1
-1 1
0 2
-1 3
1 3
4