Can you see 2 more squares here?
Many thanks to Clive Fraser aka CSFPython for this puzzle!
In this problem you will be given the x,y coordinates of a number of points in the x-y plane.
All x and y values are integers and all of these points will be less than 40 units from each of the
coordinate axes. If you take 4 of the points at random they can be joined to form a quadrilateral.
The quadrilateral will be a square only if the lengths of all 4 edges are exactly the same and if all 4
vertex angles are exactly 90 degrees. Most sets of 4 points taken at random will not form squares but many
will. Your task is to find out exactly how many of the sets of 4 points (taken from the set of given points)
form squares. Individual points and edges can belong to more than one square. However, when a set of 4 points
which form a square has been found, a simple rearrangement of the 4 points does not count as a different square.
In the example given below we have the coordinates of 13 different points. From these points it is possible to
make 5 different squares. These are described below by the corresponding sets of 4 vertex points and the
edge length in each case.
{(2,0),(2,1),(3,1),(3,0)} Edge length 1
{(2,0),(1,1),(2,2),(3,1)} Edge length 1.414
{(0,0),(0,2),(2,2),(2,0)} Edge length 2
{(0,2),(0,4),(2,4),(2,2)} Edge length 2
{(0,-2),(-2,0),(0,2),(2,0)} Edge length 2.828
Note that the actual problem will have a very much larger number of points.
Input and Answer
The first line of the problem will be a single integer N denoting the number of points.
The next line will contain 2N space-separated integers. These are the x,y coordinates of the N points.
The line should be read as:
x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 ...
The required answer is a single integer, the number of squares that can be made from the set of points.
Example:
input:
13
-2 0 0 -2 0 0 0 2 0 4 1 1 2 0 2 1 2 2 2 4 3 0 3 1 4 1
answer:
5