问题
군대 내에서 유선전화를 사용할 시 습관적으로 붙이는 머리말이다.
통신보안을 유지하자라는 말을 상기시키는 목적이 있는 것으로 사료되지만 대다수의 군인들에게는 "여보세요"를 대신하여 조건반사적으로 튀어나오는 말일 뿐이다.
군대에서 통신보안은 매우 중요하다. 최고의 IT 강국인 정올국은 더더욱 통신보안의 중요성을 알기 때문에 군사 시설 내에서의 통신을 포함한 모든 전파를 외부에서 접근하지 못하도록 차단하고 있다.
정올국의 모든 군사 시설을 감싸는 볼록 다각형 모양의 장벽을 건설한 것인데, 이 장벽은 전파를 흡수하는 신소재로 이루어져 있어 내부의 전파가 다각형 밖으로 새어나가지 못한다.
또, 통신을 일반적인 라디오로 하지 않고 레이저를 이용한다. 이로 인해 어떤 초소 A와 B가 통신을 한다고 하면, 장벽이 없어도 A와 B를 잇는 직선 위에서만 감청이 가능하다. 하지만 지금은 장벽이 있기 때문에 A와 B를 잇는 직선 위에 있으면서, 장벽 내부에 있는 점에서만 이 통신을 감청할 수 있다.
정올국의 국방장관인 한컴이는 문득 장벽이 파괴된다면, 몇 쌍의 통신을 외부에서 감청할 가능성이 있는지 살펴보고자 한다.
초소 A와 초소 B 사이의 레이저 통신을 감청하기 위해서는 X-A-B-Y의 형태로, X와 Y 위치에 감청 장치를 설치해야 하기 때문에 구체적으로 다음의 값을 구하고 싶다.
"장벽을 이루는 선분 두 개가 사라질 때, 초소 A와 초소 B를 잇는 직선이 장벽과 겹치지 않는 쌍의 개수"
输入
첫 줄에 테스트 케이스의 개수 T(1<=T<=200000)가 주어지고, 각 테스트 케이스 별로 다음의 정보가 주어진다.
첫 줄에 장벽을 이루는 꼭짓점의 개수 N(3<=N<=10)이 주어진다.
다음 줄부터 N개의 줄에 걸쳐 꼭짓점의 좌표가 시계방향 순서로 주어지고, 그 순서로 0번, 1번, ..., N-1번으로 번호를 매긴다.
그 이후 초소의 개수 M(1<=M<=50000)이 주어진다.
다음 줄부터 M개의 줄에 걸쳐 초소의 좌표가 주어진다. 이때 모든 초소는 장벽 내부에 있다.
그 이후 사라질 장벽 쌍의 개수 Q(1<=Q<=10)이 주어진다.
다음 줄부터 Q개의 줄에 걸쳐 지울 장벽의 정보 A, B가 주어진다. (0<=A, B<N)
이때 i번 장벽은 i번 꼭짓점과 (i+1)mod N번 꼭짓점을 잇는 선분을 뜻한다.
문제에서 주어지는 어떤 세 좌표도 한 직선 위에 있지 않다.
输出
각 테스트 케이스별로, Q개의 쿼리에 대한 답을 한 줄에 출력하고, 테스트 케이스 끼리는 줄바꿈으로 구분하여라.
示例
2
5
0 0
0 5
3 7
6 5
6 0
4
1 2
1 3
5 2
5 3
3
0 3
1 4
1 2
4
-1 -1
-1 1
2 1
2 -1
2
0 0
1 0
6
0 1
0 2
0 3
1 2
1 3
2 3
4 1 0
0 1 0 0 0 0
需要登录才能编写代码。