题意:给出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; }