题意:给定 n 个等腰直角三角形直角顶点在坐标系上的位置,保证斜边在 x 轴上,问有多少个三角形没有被其他三角形完全覆盖?
蒟蒻的思路:想象一个坐标系,每读入一个顶点坐标,就把这个三角形覆盖的所有顶点的坐标打上标记。如果一个三角形的顶点没有被标记,那么就没有被完全覆盖,若果被标记了,那么总数减一,最后输出就可以了。
蒟蒻的代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<list>
#include<math.h>
#include<cctype>
#include<map>
#include<stack>
#define maxn 10010
using namespace std;
typedef long long ll;
typedef unsigned long wf;
typedef unsigned int u32;
typedef unsigned long long u64;
int n,a[maxn],b[maxn],c[maxn],f[maxn][maxn],ans;
int main(){
// freopen("triangle.in","r",stdin);
// freopen("triangle.out","w",stdout);
cin>>n;
ans=n;
int x,y;
for(int k=1;k<=n;k++){
cin>>x>>y;
if(f[x][y]==n){
ans--;
continue;
}
for(int i=1;i<=x;i++){
int jx=x-y+i-1,jy=x+y-i+1;
for(int j=jx;j<=jy;j++)
f[j][i]=n;
}
f[x][y]=n;
}
cout<<ans;
return 0;
}
最后,求原题出处,感谢!