Vjudge contest 424196-Problem A

关于这道题目你发现你不需要考虑的是分割之后具体的面积是多少，我们可以用叉积计算之后暂时不除以 \(2\) ，最后判断一下奇偶性就可以了。

考虑这样的话我们就可以直接对于一个右（这里的左右实际上就是凸包上点的遍历顺序）端点，把其左端点的值存入一个桶里，发现桶内只需要存 \(x_i\) 的奇偶性， \(y_i\) 的奇偶性， \(pre_i\) 的奇偶性。

然后对于根据桶内数据求出来的面积的奇偶性判断是否可行，然后加几个特判就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,sum=0,res=0;
int pre[N],cnt[2][2][2];
struct Point{int x,y;}a[N];
signed main(){
	freopen("integral.in","r",stdin);
	freopen("integral.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i) scanf("%lld%lld",&a[i].x,&a[i].y);
	a[0]=a[n];
	for(int i=0;i<=n;++i) a[i].x&=1,a[i].y&=1;
	for(int i=1;i<=n;++i) pre[i]=(pre[i-1]^(a[i].x&a[i-1].y)^(a[i].y&a[i-1].x));
	if(pre[n]) return printf("0\n"),0;
	for(int i=1;i<n;++i){
		for(int c=0;c<2;++c){
			for(int d=0;d<2;++d){
				for(int e=0;e<2;++e){
					int tmp1=((c&a[i].y)^(d&a[i].x)),tmp2=(pre[i]^e);
					if((tmp1^tmp2)==0){
						res+=cnt[c][d][e];
						// if(cnt[c][d][e]) printf("%d %d %d %d\n",i,c,d,e);
					}
				}
			}
		}
		cnt[a[i-1].x][a[i-1].y][pre[i-1]]++;
		// printf("%lld\n",res);
	}
	printf("%lld\n",res-1);
	return 0;
}