Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
3
Indexable
Never
#include <iostream>
#define N 505

using namespace std;
int n;
int x[N],y[N],r[N];
bool ans;
int nhay(int i, int j)
{
	int kc=((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
	int u=(r[i]+r[j]);
	if(kc<=((40+u)*(40+u)))return 1;
	if(kc<=((90+u)*(90+u)))return 2;
	return 3;
}
int kc[N][N];
int dd[N][N];
int sx[N*N];
int sy[N*N];
void doc()
{
	ans=false;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>r[i];
	}
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)kc[i][j]=kc[j][i]=nhay(i,j);
}

void bfs()
{
	int dau=1,cuoi=0;
	sx[++cuoi]=1;
	sy[cuoi]=0;
	dd[1][0]=1;
	while(dau<=cuoi)
	{
		int u=sx[dau];
		int v=sy[dau];
		//cout<<u<<" "<<v<<" "<<dd[u][v]<<"\n";
		dau++;
		for(int j=1;j<=n;j++)
		{
			int r=kc[u][j];
			if(r==1)
			{
				if(dd[j][v]==0)
				{
					dd[j][v]=dd[u][v]+1;
					sx[++cuoi]=j;
					sy[cuoi]=v;
				}
			}else if(r==2&&v<n-1)
			{
				if(dd[j][v+1]==0)
				{
					dd[j][v+1]=dd[u][v];
					sx[++cuoi]=j;
					sy[cuoi]=v+1;
				}
			}
		}
	}
}
int TC;
int main()
{
//	freopen("input.txt","r",stdin);
	
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
		//cout<<"Case #"<<tc<<"\n";
		doc();
		for(int i=1;i<=n;i++)
			for(int j=0;j<n;j++)dd[i][j]=0;
		bfs();
		for(int i=0;i<n;i++)if(dd[n][i])
		{
			cout<<i<<" "<<dd[n][i]-1<<"\n";
			ans=true;
			break;
		}
		if(!ans)cout<<-1<<"\n";
	}
	
		return 0;
}