题目描述：

给你n（1000）个点的2维坐标，没有三点共线的情况，有m（1000000）次查询，每次查询给你abc三个数，问你abc这三个点构成的三角形内有多少个点。

解题报告：

 

http://s11/middle/64675f54g927bf865c45a&6901973 计算几何 The 35th ACM/ICPC Asia Regional Fuzhou Site" TITLE="FZU 1973 计算几何 The 35th ACM/ICPC Asia Regional Fuzhou Site" />

如图，给你abc三个点，我可以把它分成7个部分。

第一步：

n²的复杂度预处理出7 + 2, 7 + 4, 7 + 6类似这样的区域内的点数。

做法：

比如求从直线ab与直线ac之间的点数，只要以a为中心点极角排序，把每个点编号，c的编号和b的编号相减就好了。

第二步：

n²的复杂度预处理出任意两点构成的直线的两边各有多少点。

比如求直线a到b的左侧有多少点。

按a点极角排序后，二分找点，找到满足在左侧的最靠左的点，和b的编号相减就好了。

第三部：

就是如何用O(1)的复杂度得到任意三点构成三角形内的点数。

由第一步预处理的结果：可以得到 7 + 2 + 7 + 4 + 7 + 6的点数，记作A1

由第二部预处理的结果：可以得到 1 + 2 + 3 + 3 + 4 + 5 + 5 + 6 + 1的点数，记作A2

然后可以得到除了A1剩余部分的点数：

         (n – 3) – A1 = 1 + 3 + 5 – 2 * 7区域的点数。记作A3（其中n – 3是除了三角形外的所有的点数）

         观察即可发现A2 – A1 – 2 * A3 = 第7号区域的点数，就是我们要的答案。

 

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct pint{long long x, y; int id;double val;} x[1100], jeo[1100], que[3];
int A[1100][1100], B[1100][1100];
long long aabs(long long x){if (x < 0) return -x; return x;}
long long cross(pint &p1, pint &p2, pint &p3)
{
    return (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y);
}
bool cmp(const pint &p1, const pint p2)
{
    return p1.val < p2.val;
}
int mmod(int x, int n)
{
    return ((x % n) + n) % n;
}
int t, n, q;
int judge(int j)
{
    int l = mmod(j + 1, n - 1), r = mmod(j - 1, n - 1);
    if (cross(jeo[n - 1], jeo[j], jeo[r]) < 0) return mmod(r - j, n - 1);
    if (cross(jeo[n - 1], jeo[j], jeo[l]) > 0) return 0;
    while(mmod(l + 1, n - 1) != r)
    {
        int mid = mmod(l + (mmod(r - l, n - 1) >> 1), n - 1);
        if (cross(jeo[n - 1], jeo[j], jeo[mid]) > 0) r = mid;
        else l = mid;
    }
    return mmod(l - j, n - 1);
}
int main()
{
    scanf("%d", &t); int ca = 1;
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%I64d%I64d", &x[i].x, &x[i].y), x[i].id = i;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                jeo[j] = x[j];
                if (j == i) continue;
                jeo[j].val = atan2((double)jeo[j].y - x[i].y, (double)jeo[j].x - x[i].x);
            }
            swap(jeo[n - 1], jeo[i]);
            sort(jeo, jeo + n - 1, cmp);
            for(int j = 0; j < n - 1; j++)
            {
                A[i][jeo[j].id] = j;
                B[i][jeo[j].id] = judge(j);
            }
        }
        printf("Case %d:\n", ca++);
        scanf("%d", &q);
        while(q--)
        {
            int tmp, id = -1, xx = 1000000, yy = 1000000;
            for(int i = 0; i < 3; i++)
            {
                scanf("%d", &tmp), que[i] = x[tmp];
                if (que[i].x < xx || (que[i].x == xx && que[i].x < yy))
                {
                    id = i;
                    xx = que[i].x, yy = que[i].y;
                }
            }
            swap(que[0], que[id]);
            for(int i = 1; i < 3; i++) que[i].val = atan2((double)que[i].y - que[0].y, (double)que[i].x - que[0].x);
            sort(que + 1, que + 3, cmp);
            int ans[6];
            for(int i = 0; i < 3; i++)
                ans[i] = mmod(A[que[i].id][que[(i + 2) % 3].id] - A[que[i].id][que[(i + 1) % 3].id], n - 1) - 1;
            for(int i = 3; i < 6; i++)
                ans[i] = n - 2 - B[que[i - 3].id][que[(i - 3 + 1) % 3].id];
            int re1 = 0, re2 = 0, re3 = 0;
            for(int i = 0; i < 3; i++) re1 += ans[i];
            for(int i = 3; i < 6; i++) re2 += ans[i];
            re3 = n - 3 - re1;
            re2 -= re1;
            re2 -= (re3 + re3);
            printf("%d\n", re2);
        }
    }
    return 0;
}