수평으로 보이는 선분

시간 제한1초메모리 제한128 MB

요약

서로 겹치지 않는 수직 선분들이 주어질 때, 세 선분이 모두 서로 수평으로 보이는 삼각형의 개수를 구하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 정렬, 기하, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

평면 위에 서로 겹치지 않는(어떤 두 선분도 공통점을 가지지 않는) 수직 선분들의 집합이 주어진다.

두 선분을 잇는 수평 선분을 그을 수 있고 그 수평 선분이 다른 어떤 수직 선분과도 공통점을 가지지 않으면, 두 선분은 서로 수평으로 보인다고 한다. 서로 다른 세 수직 선분에서 세 쌍이 모두 서로 수평으로 보이면, 이 세 선분은 하나의 선분 삼각형을 이룬다.

각 데이터 집합마다 수직 선분들의 정보를 읽고, 그 안에 선분 삼각형이 몇 개 있는지 세어라.

입력

첫째 줄에는 데이터 집합의 개수를 나타내는 양의 정수 $d$ 가 주어지며, $1 \le d \le 20$ 이다. 그다음에 각 데이터 집합이 이어진다.

각 데이터 집합의 첫째 줄에는 수직 선분의 개수를 나타내는 정수 $n$ 이 주어지며, $1 \le n \le 8000$ 이다. 이어지는 $n$ 개의 줄에는 각각 세 개의 음이 아닌 정수 $y_i'$ , $y_i''$ , $x_i$ 가 공백 하나로 구분되어 주어진다. 이는 각각 $i$ 번째 선분의 아래쪽 끝점의 $y$ 좌표, 위쪽 끝점의 $y$ 좌표, 그리고 $x$ 좌표이다. 좌표는 $0 \le y_i' < y_i'' \le 8000$ 과 $0 \le x_i \le 8000$ 을 만족하며, 선분들은 서로 겹치지 않는다.

출력

정확히 $d$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 데이터 집합에 들어 있는 선분 삼각형의 개수를 나타내는 정수 하나를 출력한다.

예제9

예제 1
입력
```
1
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
```
예상 출력
```
1
```
예제 2
입력
```
1
1
0 5 0
```
예상 출력
```
0
```
예제 3
입력
```
1
3
0 10 0
0 3 1
0 10 2
```
예상 출력
```
1
```
예제 4
입력
```
1
3
0 10 0
0 10 1
0 10 2
```
예상 출력
```
0
```

예제 5

입력

예상 출력

1
0
1

예제 6
입력
```
1
3
0 3 1
3 6 2
0 6 3
```
예상 출력
```
1
```
예제 7
입력
```
1
4
0 20 0
0 1 1
3 4 1
6 7 1
```
예상 출력
```
0
```
예제 8
입력
```
1
5
0 1 0
0 1 1
0 1 2
0 1 3
0 1 4
```
예상 출력
```
0
```
예제 9
입력
```
1
2
0 2 5
5 7 5
```
예상 출력
```
0
```