Non-interger Area 分类讨论 奇偶 取模 牛客练习赛95

Non-interger Area 分类讨论 奇偶 取模 牛客练习赛95

链接：https://ac.nowcoder.com/acm/contest/11185/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
给定平面上 nn 个整点（横纵坐标均为整数的点）（可能重合），编号为 A_1sim A_nA
1
​
∼A
n
​
，从中选出三个编号不同的点 A_i,A_j,A_kA
i
​
,A
j
​
,A
k
​
（其中 ii 小于 jj 小于 kk）组成一个三角形。有几种选法使得三角形的面积不是整数？
输入描述:
第一行一个正整数 n (1le nle 10^5)n (1≤n≤10
5
)。

接下来 nn 行，第 ii 行两个整数 x,yx,y，表示 A_i=(x,y)A
i
​
=(x,y)。(|x|,|y|le 10^{18})(∣x∣,∣y∣≤10
18
)
输出描述:
输出一行一个非负整数，为答案。
示例1
输入
复制
3
0 0
1 1
2 2
输出
复制
0
示例2
输入
复制
6
0 0
2 2
2 3
4 6
-5 1
-4 3
输出
复制
6

思路 ：

由面积公式 S = 1 2 ∣ ( x i − x z ) ∗ ( y j − y z ) − ( x j − x z ) ∗ ( y i − y z ) ∣ S=frac{1}{2}|(x_i-x_z)*(y_j-y_z)-(x_j-x_z)*(y_i-y_z)| S=21​∣(xi​−xz​)∗(yj​−yz​)−(xj​−xz​)∗(yi​−yz​)∣，得知面积是否为偶数与所选三个点的横纵坐标的奇偶性相关，这样一共有 2 6 2^6 26种情况又因为每次选择以一整个点为单位，因此按输入每一个点的横纵坐标奇偶性直接存储个数最后，由于所选三个点有顺序，答案除以 A 3 3 = 6 A^3_3=6 A33​=6注意最后才除以6，不能在枚举中直接除以6

#include 
using namespace std;

typedef long long ll;

ll cnt[3][3];

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        ll x, y; cin >> x >> y;
        cnt[(x % 2 + 2) % 2][(y % 2 + 2) % 2] ++ ;
    }
    
    ll res = 0;
    for (int a = 0; a < 2; a ++ )
        for (int b = 0; b < 2; b ++ )
            for (int c = 0; c < 2; c ++ )
                for (int d = 0; d < 2; d ++ )
                    for (int e = 0; e < 2; e ++ )
                        for (int f = 0; f < 2; f ++ )
                        {
                            int t = (a - b) * (c - d) - (e - b) * (f - d);
                            if ((t % 2 + 2) % 2 == 1)
                                res += cnt[a][f] * cnt[b][d] * cnt[e][c];
                        }
    cout << res / 6ll;
}