496. L-Shapes
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Let's say that two line segments of non-zero length form an
if they are at a
angle to each other and one endpoint of one segment coincides with one endpoint of the other.
There are
N line segments on a plane. The segments are numbered from 1 to
N. Count the number of distinct pairs of segments that form L-shapes. Two pairs are considered distinct if they contain segments with different numbers.
Input
The first line of the input line contains the integer
N (1 ≤
N ≤ 5000). Each of the following
N lines describes one segment and contains four integers
x1,
y1,
x2,
y2 (
), where (
x1,
y1) and (
x2,
y2) are endpoints of the segment. It may be assumed that for each segment
x1 ≠q
x2 or
y1 ≠q
y2.
Output
The output file should contain a single integer, the total number of distinct pairs of line segments forming L-shapes.
Example(s)
sample input | sample output |
7
0 4 0 7
4 4 1 6
1 6 -3 0
4 4 0 4
0 0 0 4
0 0 0 2
0 4 4 4
|
5
|
Note. In the example the L-shapes are formed by the following pairs of segments: (1, 4), (1, 7), (2, 3), (4, 5), (5, 7). Note that the segments 4 and 7 coincide, but the pairs (1, 4) and (1, 7), for example, are still considered distinct.