数组并不大,为何会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
*/