提示: 欢迎访问OurACM平台。
Problem 1973 How many stars

Accept: 217    Submit: 720
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

John has a telescope and he always observes the stars. After each observation, John draws all stars on a paper. To simplify the problem, each star is described as a distinct point in two-dimensional space and no three points are in a line.

There are N stars on the paper. John is so boring that he wants to find some ways to kill the time. He chooses three different points random to form a triangle, and then he wants to know the number of points inside this triangle. There is only one point inside the triangle in Figure 1.

Figrue 1

Input

The first line of the input contains an integer T (T≤10), indicating the number of cases. Each case begins with a line containing an integer N (3≤N≤1,000), the number of points in the paper. Each of the following N lines contains two integers Xi and Yi 0≤|Xi|, |Yi|≤100,000, 1≤i≤N). The next line contains an integer M (0≤M≤1,000,000), the number of queries John will do. Each of the following M lines contains three integers x, y and z (0≤x, y, z<N), the index of the points John has chosen. The stars are labeled from 0 to N-1.

Output

For each test case, print a line containing the test case number (beginning with 1) on its own line, then the answers for each query, one on each line.

Sample Input

2 4 1 1 0 0 0 1 1 0 1 2 1 0 5 0 0 5 0 5 5 0 5 2 1 2 3 1 2 2 0 1

Sample Output

Case 1: 0 Case 2: 0 1

Source

The 35th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest

Submit  Back  Status  Discuss