题目分析

这道题目要求我们计算给定点集中可以组成多少个面积为整数的三角形（包括退化的三角形，即面积为0的情况）。关键在于利用三角形面积公式来高效判断面积是否为整数。

解题思路

1. 数学观察：三角形面积公式为： $A = |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)| / 2$ 要使A为整数，分子必须是偶数。

2. 奇偶性分析：通过分析坐标的奇偶性，可以发现：

   • 如果三个点的坐标奇偶性组合满足特定模式，面积一定是整数。
   • 特别地，当三个点中有两个点的x或y坐标奇偶性相同时，面积更可能是整数。

3. 组合计数：

   • 总三角形数为C(n,3)。
   • 减去那些面积非整数的三角形组合数。

标程代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long cnt[2][2],n,x,y;
int main(){
    int t;
    int flag=1;
    scanf("%d",&t);
    while(t--){
        cnt[0][0]=cnt[1][0]=cnt[0][1]=cnt[1][1]=0;
        scanf("%lld",&n);
        for(int i=0;i<n;i++){
            scanf("%lld%lld",&x,&y);
            cnt[x&1][y&1]++;
        }
        long long ans=n*(n-1)*(n-2)/6;
        ans-=cnt[0][0]*cnt[0][1]*cnt[1][0];
        ans-=cnt[0][0]*cnt[0][1]*cnt[1][1];
        ans-=cnt[0][0]*cnt[1][0]*cnt[1][1];
        ans-=cnt[0][1]*cnt[1][0]*cnt[1][1];
        printf("Scenario #%d:\n",flag);
        flag++;
        printf("%lld\n\n",ans);
    }
 
    return 0;
}

代码说明

1. 输入处理：读取测试用例数量和每个测试用例的点集。
2. 奇偶性统计：统计每个点坐标的奇偶性组合。
3. 组合计算：
   • 计算所有可能的三角形组合数C(n,3)。
   • 减去那些面积非整数的三角形组合数。
4. 输出结果：按要求格式输出每个场景的结果。

该方法通过数学观察和组合计数高效解决问题，时间复杂度为O(n)，适用于大规模输入。