POJ 1809 Regetni 奇偶性

本文主要是介绍POJ 1809 Regetni 奇偶性，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你许n个点，可以从中任选三个点组成一个三角形。问这些三角形中面积为整数的有多少（包括0）。

题中给出一个面积公式：A=|x1y2 - y1x2 + x2y3 - y2x3 + x3y1 - y3x1|/2 

题解：本质上我们只要让x1y2 ，y1x2 ， x2y3，y2x3， x3y1 ，y3x1这六项中奇数项的个数为偶数个，即0,2,4,6。

所以我们把点分类：奇奇，偶偶，奇偶，偶奇。逐个分析之后可以发现，只要保证三个顶点中至少有两个属于同一类，就能保证有偶数个 奇数项。

#include<cstdio>
using namespace std;#define lint __int64
int a[4];lint C ( int m, int n )
{if ( m < n ) return 0;if ( m == n || n == 0) return 1;lint mult = 1;for ( int i = 1, j = m; i <= n; i++, j-- )mult = mult * j / i;return mult;
}int main()
{int t, n, x, y;scanf("%d",&t);for ( int i = 1; i <= t; i++ ){scanf("%d",&n);a[0] = a[1] = a[2] = a[3] = 0;while ( n-- ){scanf("%d%d",&x,&y);if ( (x&1) && (y&1) ) a[0]++;else if ( !(x&1) && !(y&1) ) a[1]++;else if ( (x&1) && !(y&1) ) a[2]++;else a[3]++;}lint ret = 0;ret += C(a[0],3)+C(a[1],3)+C(a[2],3)+C(a[3],3);ret += C(a[0],2) * (a[1]+a[2]+a[3]);ret += C(a[1],2) * (a[0]+a[2]+a[3]);ret += C(a[2],2) * (a[1]+a[0]+a[3]);ret += C(a[3],2) * (a[1]+a[2]+a[0]);printf("Scenario #%d:\n%I64d\n\n",i,ret);}return 0;
}

这篇关于POJ 1809 Regetni 奇偶性的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---