102
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;
}
最后更新：2017-04-03 16:48:45