求助一道题(模拟赛时本地能过,结果爆零)
  • 板块学术版
  • 楼主Vigilant_Yaksha
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/10/27 13:10
  • 上次更新2023/10/27 05:38:40
查看原帖
求助一道题(模拟赛时本地能过,结果爆零)
579489
Vigilant_Yaksha楼主2022/10/27 13:10

题意:给定 nn 个等腰直角三角形直角顶点在坐标系上的位置,保证斜边在 xx 轴上,问有多少个三角形没有被其他三角形完全覆盖?

蒟蒻的思路:想象一个坐标系,每读入一个顶点坐标,就把这个三角形覆盖的所有顶点的坐标打上标记。如果一个三角形的顶点没有被标记,那么就没有被完全覆盖,若果被标记了,那么总数减一,最后输出就可以了。

蒟蒻的代码:

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

最后,求原题出处,感谢!

2022/10/27 13:10
加载中...