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