시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 8 | 7 | 7 | 100.000% |
Let's say that three segments on a plane form a K-shaped figure if:
$\{AB,CD,CE\}$ | $\{AB,CD,CE\}$ | $\{AB,CD,CE\}$ | $\{AB,CD,CE\}$ | $\{AB,CD,CE\}$ | $\{AB,CD,EF\}$ | $\{AB,AC,AD\}$ |
Valid K-shaped figures | Invalid K-shaped figures |
You are given a collection of $n$ segments on the plane. Find the number of triples of segments from this collection that form a K-shaped figure.
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 3333$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ --- the number of segments ($3 \le n \le 1000$).
The $i$-th of the following $n$ lines contains four integers $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$ --- the coordinates of endpoints of the $i$-th segment ($-10^6 \le x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2} \le 10^6$). All segments have positive lengths. Some segments may coincide.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.
For each test case, print a single integer --- the number of triples of segments that form a K-shaped figure.
2 5 0 0 0 10 0 5 3 10 0 5 3 0 0 5 7 4 0 5 6 2 8 0 0 10 10 3 4 4 4 4 4 4 5 3 4 4 4 7 7 7 8 7 7 8 7 5 5 4 6 5 5 3 7
6 2