CF2009D 题解

coderJerry · 2024-10-05 10:42:16 · 题解

分类讨论题。

样例第一组测试数据的动图，可以查看帮助理解（如果图挂了到 CF 上看）。 #

• case 1：两条直角边垂直于两坐标轴的，

这个时候其中一条直角边的两端点必定是 (t,0),(t,1)。另外 n-2 个点都能和这条线段组成直角三角形。

• case 2：45 度的等腰直角三角形，且两条直角边都不垂直于坐标轴的，

  • • 直角顶点是 (t,0)，
  • 这个时候另外两个顶点就必定是 (t-1,1),(t+1,1)。
  • • 同理，当直角顶点是 (t,1) 时，
  • 这个时候另外两个顶点就必定是 (t-1,0),(t+1,0)。

枚举每个点是否符合上述情况，统计即可。 # 清空不彻底，被hack两行泪！

赛时代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int v[200010][2];//v[x][y] 表示 (x,y) 是否出现过
signed main(){
    int t,x,y,n,ans=0;
    cin>>t;
    while(t--){
        ans=0;
        cin>>n;
        for(int i=0;i<=200000;i++){v[i][0]=v[i][1]=0;}//清空不彻底，被hack两行泪！
        for(int i=1;i<=n;i++){
            cin>>x>>y;
            v[x][y]=1;
        }
        for(int i=0;i<=n;i++){
            if(v[i][0]==1&&v[i][1]==1)ans+=(n-2);//case1
            if(v[i][1]==1&&v[i-1][0]==1&&v[i+1][0]==1)ans++;//case2-1
            if(v[i][0]==1&&v[i-1][1]==1&&v[i+1][1]==1)ans++;//case2-2
        }
        cout<<ans<<endl;
    }
    return 0;
}