주조 (Casting)

주조(casting)는 만들려는 물체 모양의 빈 공간이 있는 거푸집(cast)에 액체를 부어 굳힌 뒤 거푸집을 떼어 내는 제조 공정이다. 같은 거푸집을 재사용하여 물체를 대량 생산하려면, 거푸집과 물체를 모두 손상하지 않고 거푸집을 물체에서 떼어 낼 수 있어야 한다.

물체가 볼록 다각형 $P$일 때, $P$의 두 꼭짓점을 지나는 직선을 따라 거푸집을 두 조각으로 나눈다. 목표는, 두 조각을 각각 평행 이동만으로 (거푸집 조각과 물체를 모두 손상하지 않고) 떼어 낼 수 있게 하는 꼭짓점 쌍을 찾는 것이다. 예를 들어 원 문제의 그림에서는 어떤 두 꼭짓점을 지나는 직선으로 나누면 위쪽 조각은 위로, 아래쪽 조각은 아래로 빼낼 수 있지만, 다른 어떤 두 꼭짓점을 지나는 직선으로 나누면 한쪽 조각이 물체를 감싸 버려 어떤 방향으로도 떼어 낼 수 없다. 즉, 모든 꼭짓점 쌍이 이런 분할을 허용하지는 않는다. (각 조각은 서로 다른 평행 이동 방향으로 빼내도 되며, 나누는 직선에 수직인 방향으로만 빼낼 수 있어야 하는 것은 아니다.)

$n$개의 꼭짓점을 가진 볼록 다각형 $P$가 주어질 때, $(v_i, v_j)$를 지나는 직선으로 나눈 두 거푸집 조각을 모두 평행 이동으로 떼어 낼 수 있는 꼭짓점 쌍 $(v_i, v_j)$를 모두 찾는 프로그램을 작성하라.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 볼록 다각형 $P$의 꼭짓점 수 $n$이 주어지며 $3 \le n \le 100{,}000$이다. 다음 줄에는 $2n$개의 정수 $x_1\ y_1\ x_2\ y_2\ \dots\ x_n\ y_n$이 주어지는데, $x_i$와 $y_i$는 각각 꼭짓점 $v_i$의 $x$좌표와 $y$좌표이다. 모든 좌표는 정수이며 $-1{,}000{,}000{,}000 \le x_i, y_i \le 1{,}000{,}000{,}000$이다. 꼭짓점 $v_1, v_2, \dots, v_n$은 $P$의 경계를 따라 시계 방향으로 주어진다.

출력은 표준 출력으로 한다. 각 테스트 케이스에 대해, $(v_i, v_j)$를 지나는 직선으로 나눈 두 거푸집 조각을 모두 평행 이동으로 떼어 낼 수 있는, $i < j$인 꼭짓점 쌍 $(v_i, v_j)$의 개수를 한 줄에 출력한다.