HDU 4380 预处理枚举

题意：给出n个房子m个矿问从n个房子选三个组成的三角形内部矿数为奇数有多少种选法。

先预处理一下每条线段正上方有多少个点，然后在枚举三条线段就可以了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct point
{
    long long x,y;
};
int cmp(point a,point b)
{
    return a.x<b.x;
}
long long Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
long long yl[205][205];
point data[205],mine[1005];
int main()
{
    int t,n,m,ca=0;
    while(~scanf("%d%d",&n,&m))
    {
        memset(yl,0,sizeof(yl));
        for(int i=0; i<n; i++)
            scanf("%I64d%I64d",&data[i].x,&data[i].y);
        for(int i=0; i<m; i++)
            scanf("%I64d%I64d",&mine[i].x,&mine[i].y);
        sort(mine,mine+m,cmp);
        sort(data,data+n,cmp);
        for(int i=0; i<n; i++)       //预处理
            for(int j=i+1; j<n; j++)
                for(int k=0; k<m&&mine[k].x<data[j].x; k++)
                    if(mine[k].x>=data[i].x&&Direction(data[i],data[j],mine[k])>0)
                        yl[i][j]++;
        long long ans=0;
        for(int i=0; i<n; i++)
            for(int j=i+1; j<n; j++)
                for(int k=j+1; k<n; k++)
                {
                    long long q=yl[i][k]-yl[i][j]-yl[j][k];
                    if(q<0) q=-q;
                    if(q%2)
                        ans++;
                }
        printf("Case %d: ",++ca);
        printf("%I64d\n",ans);
    }
    return 0;
}