鏈接：https://ac.nowcoder.com/acm/contest/11185/B
來源：?？途W

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 524288K，其他語言1048576K
64bit IO Format: %lld
題目描述
給定平面上 nn 個整點（橫縱坐標均為整數的點）（可能重合），編號為 A_1\sim A_nA
1
?
～A
n
?
，從中選出三個編號不同的點 A_i,A_j,A_kA
i
?
,A
j
?
,A
k
?
（其中 ii 小于 jj 小于 kk）組成一個三角形。有幾種選法使得三角形的面積不是整數？
輸入描述:
第一行一個正整數 n\ (1\le n\le 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=\frac{1}{2}|(x_i?x_z)?(y_j?y_z)?(x_j?x_z)?(y_i?y_z)|$，得知面積是否為偶數與所選三個點的橫縱坐標的奇偶性相關，這樣一共有$2^6$種情況
• 又因為每次選擇以一整個點為單位，因此按輸入每一個點的橫縱坐標奇偶性直接存儲個數
• 最后，由于所選三個點有順序，答案除以$A_3^3=6$
• 注意最后才除以6，不能在枚舉中直接除以6

#include <iostream> 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; }

總結

以上是生活随笔為你收集整理的Non-interger Area 分类讨论 奇偶 取模 牛客练习赛95的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。