Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.4 kB
1
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Scanner;

public class CopyOfTheFrog {
	static {
		try {
			System.setIn(new FileInputStream("src/inp.txt"));
			// System.setOut(new PrintStream("src/out.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	static Scanner scanner = new Scanner(System.in);

	static void exec(int test) {
		int n=Integer.parseInt(scanner.next());
		int[] x=new int[n],y=new int[n],r=new int[n];
		for(int u=0;u<n;++u){
			x[u]=Integer.parseInt(scanner.next());
			y[u]=Integer.parseInt(scanner.next());
			r[u]=Integer.parseInt(scanner.next());
		}
		
		long cost[][]=new long[n][n];
		//khoi tao ma tran trong so
		//kiem tra xem khoang cach giua 2 la sen tru ban kinh giua 2 la sen 
		//<=40 => nhay gan dat la 1
		//<=90 => nhay xa dat la n (do neu nhay gan vs trong so 1 thi chi nhay toi da n-1 lan, trong so toi da la n-1 => de chia du sau nay
		for(int u=0;u<n;++u)
			for(int v=0;v<n;++v)
				if(u!=v){
					long c2=(x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]);
					long right=(40+r[u]+r[v])*(40+r[u]+r[v]);
					long right2=(90+r[u]+r[v])*(90+r[u]+r[v]);
					if(c2<=right)
						cost[u][v]=1;
					else if(c2<=right2)
						cost[u][v]=n;
				}
		//dijktra tim quang duong ngan nhat
		//do trong quang duong ngan nhat thi trong so cua trong luong xa chiem dang ke
		//nen tim qdnn tuong ung vs so buoc di vs trog so max nho nhat
		boolean[] M=new boolean[n];
		long[] res=new long[n];
		for(int u=0;u<n;++u)
			res[u]=Long.MAX_VALUE;
		res[0]=0;
		for(int i=1;i<n;++i){
			int u=-1;
			long costu=Long.MAX_VALUE;
			for(int v=0;v<n;++v)
				if(!M[v] && costu>res[v]){
					costu=res[v];
					u=v;
				}
			if(u==-1)
				break;
			M[u]=true;
			for(int v=0;v<n;++v)
				if(!M[v] && cost[u][v]>0 && res[v]>costu+cost[u][v])
					res[v]=costu+cost[u][v];
		}
		
		//so quang duong vs trong so max*trong so max + so qd trong so min
		if(res[n-1]==Long.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.printf("%d %d\n",res[n-1]/n,res[n-1]%n);
	}

	public static void main(String[] args) {
		int t = Integer.parseInt(scanner.next());

		for (int test = 1; test <= t; ++test)
			exec(test);

		scanner.close();
	}
}