Hide

Problem I
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 1,2,3,4 in the picture form a square if lines 1 and 3 are parallel to each other and perpendicular to 2 and 4, and moreover the distance between 1 and 3 is the same as the distance between 2 and 4.

Input

The first line of the input contains a single integer n (1n2 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 x1,y1,x2,y2, each of them of absolute value at most 10 000, such that the line passes through points (x1,y1) and (x2,y2). You may assume that points (x1,y1) and (x2,y2) 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
Hide

Please log in to submit a solution to this problem

Log in