迷之MLE???
查看原帖
迷之MLE???
387277
___OvO___楼主2020/10/3 23:31

数组并不大,为何会MLE,求daolao指教;

#include<bits/stdc++.h>
using namespace std;
bool ans[1500];
struct point{
	double x;
    double y;
    double z;

}a[1005];
bool cmp(point c,point d)
{
	if(c.z!=d.z)return c.z<d.z;
	else if(c.y!=d.y)return c.y<d.y;
	     else return c.x<d.x; 
}
double dist(int i1,int i2)
{
	return (a[i1].x-a[i2].x)*(a[i1].x-a[i2].x)+(a[i1].y-a[i2].y)*(a[i1].y-a[i2].y)+(a[i1].z-a[i2].z)*(a[i1].z-a[i2].z);
}
bool df=0;
int back[1500];
void dfs(int x,int n,int r,int h)
{
/*	int ne=n;
	for(int t=i;t<=ne;t++)
	{
	//	if(df)return true;
		if(dist(i,t)<=4*r*r){
			if(a[t].z>=h-r)/*df=1 return true;
			if(t+1<=n){
				if(dfs(t+1,n,r,h))return true;
			}
	    }
		//else ne=t+10;
	}
	return false;*/
	if(df==1) return;
    if(a[x].z+r>=h) {
        df=1;
        return;
    }
    for(int i=x;i<=n;i++) {
        //if(m[i]==1) continue;
        if(dist(i,x)<=4*r*r){
          //  m[i]=1;
            dfs(i,n,r,h);
        }
    }
}
int main()
{
	int T;
	cin>>T;
	int n,h,r,x,y,z;
	for(int q=1;q<=T;q++){
		cin>>n>>h>>r;
		bool f1=0;
		bool f2=0;
		bool f3=0;
		int o=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
			if(a[i].z<=r){
				o++;
				back[o]=i;
				f1=1;
			}
			if(a[i].z>=h-r)f2=1;
		}
		sort(a+1,a+n+1,cmp);
		
		for(int u=1;u<=o;u++)
		{
		    df=0;
			dfs(u,n,r,h);
			if(df){
				f3=1;
				break;
			}
		}
		
		if(f1&&f2&&f3)ans[q]=1;
	  else ans[q]=0;
	}
	for(int i=1;i<=T;i++)
	{
		if(ans[i])cout<<"Yes"<<endl;
	  else cout<<"No"<<endl;
	}
}
/*
5
1 100 60
70 27 88
1 100 75
80 39 34
1 100 50
605 563 50
1 200 160
120 176 40
1 200 105
0 47 84
*/
2020/10/3 23:31
加载中...