Hide

Problem D
How many squares?

/problems/squares/file/statement/en/img-0001.jpg
Hemocytometer, a device for counting blood cells; by Jeffrey M. Vinocur under CC BY 2.5

While browsing the internet, of course using Internet Explorer without any adblocker, you have noticed a number of interesting competitions advertised in the panels on various webpages. In most of these competitions you need to answer a simple question, like how many triangles/squares/rectangles there are in a picture, or even choose the right answer out of three possibilities. Despite the simplicity of the task, it seems that there are many valuable prizes to be won. So there is definitely something to compete for!

In order to increase your chances, you decided to write a simple program that will solve the problem for you. You decided to focus first on the question “How many squares are there in the picture?”, and to simplify the problem even more, you assume that the input picture consists only of a number of lines that are infinite in both directions. To be precise, we say that four lines $\ell _1,\ell _2,\ell _3,\ell _4$ in the picture form a square if lines $\ell _1$ and $\ell _3$ are parallel to each other and perpendicular to $\ell _2$ and $\ell _4$, and moreover the distance between $\ell _1$ and $\ell _3$ is the same as the distance between $\ell _2$ and $\ell _4$.

Input

The first line of the input contains a single integer $n$ ($1\leq n\leq 2\ 000$), denoting the number of lines in the input picture. Then follow $n$ lines, each containing a description of one line in the input picture. The line is given as a pair of distinct points lying on it. That is, the description consists of four integers $x_1,y_1,x_2,y_2$, each of them of absolute value at most $10\ 000$, such that the line passes through points $(x_1,y_1)$ and $(x_2,y_2)$. You may assume that points $(x_1,y_1)$ and $(x_2,y_2)$ are different, and also that all the lines in the picture are pairwise different.

Output

Output exactly one line with one integer, denoting the total number of squares formed by the lines in the picture.

Sample Input 1 Sample Output 1
10
0 0 1 0
0 1 1 1
0 2 2 2
0 0 0 4
1 -1 1 0
2 -2 2 2
1 1 2 2
1 1 0 2
3 1 2 2
1 3 0 2
6

Please log in to submit a solution to this problem

Log in