Untitled
unknown
plain_text
a month ago
4.1 kB
1
Indexable
Never
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int N; static int[][] arr = new int[205][3]; static int[][] dis = new int[205][205]; static int[] visit = new int[205]; static int[] time = new int[205]; static pQueue queue = new pQueue(400000); public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub System.setIn(new FileInputStream("src/input2.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int t = 1; t <= T; t++) { N = sc.nextInt(); for (int i = 0; i < N; i++) { visit[i] = 0; if (i != 0) { time[i] = Integer.MAX_VALUE; } for (int j = 0; j < 3; j++) { arr[i][j] = sc.nextInt(); dis[i][j] = 0; } } dis = calDist(); // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // System.out.print(dis[i][j] + " "); // } // System.out.println(); // } // // System.out.println(); queue.reset(); for (int i = 0; i < N; i++) { if (i != 0) { time[i] = dis[0][i]; queue.push(0, i, dis[0][i]); } } int[] tmp; int xa = 0; int gan = 0; int s, e, d; boolean check = true; visit[0] = 1; while (!queue.empty() && check) { tmp = queue.pop(); s = tmp[0]; e = tmp[1]; d = dis[s][e]; if (d <= 40 * 40) { gan++; } if (d <= 90 * 90 && d > 40 * 40) { xa++; } if (d > 90 * 90) { xa = gan = -1; check = false; } ; if (e == N - 1) break; visit[e] = 1; for (int i = 0; i < N; i++) { if (visit[i] == 0) { if (time[i] > dis[e][i] + time[e]) { time[i] = dis[e][i] + time[e]; queue.push(e, i, time[i]); } } } } if (!check) { System.out.println(-1); } else { System.out.println(xa + " " + gan); } } sc.close(); } private static int[][] calDist() { for (int i = 0; i < N; i++) { int x = arr[i][0]; int y = arr[i][1]; int r = arr[i][2]; int dist = 0; for (int j = 0; j < N; j++) { if (j != i) { dist = (x - arr[j][0]) * (x - arr[j][0]) + (y - arr[j][1]) * (y - arr[j][1]); dist = dist - (arr[j][2] + r); dis[i][j] = dist; } } } return dis; } } class pQueue { static int capacity, size, lChild, rChild, parent, child, larger; static int[][] arr; static int[] tmp, res; pQueue(int c) { capacity = c; size = 0; arr = new int[capacity][3]; tmp = new int[3]; res = new int[3]; } void push(int x, int y, int z) { arr[size][0] = x; arr[size][1] = y; arr[size][2] = z; size++; heapUp(); } int[] pop() { for (int i = 0; i < 3; i++) { res[i] = arr[0][i]; arr[0][i] = arr[size - 1][i]; } size--; heapDown(); return res; } private void heapDown() { // TODO Auto-generated method stub parent = 0; while (true) { lChild = parent * 2 + 1; rChild = parent * 2 + 2; larger = lChild; if (rChild < size && arr[rChild][2] < arr[larger][2]) { larger = rChild; } if (larger < size && arr[larger][2] < arr[parent][2]) { swap(larger, parent); parent = larger; } else { break; } } } private void heapUp() { // TODO Auto-generated method stub child = size - 1; while (child != 0) { int parent = (child - 1) / 2; if (arr[child][2] < arr[parent][2]) { swap(child, parent); child = parent; } else { break; } } } private void swap(int c, int p) { // TODO Auto-generated method stub for (int i = 0; i < 3; i++) { tmp[i] = arr[c][i]; arr[c][i] = arr[p][i]; arr[p][i] = tmp[i]; } } boolean empty() { return size == 0; } int size() { return size; } int[] valueOf(int idx) { return arr[idx]; } void reset() { size = 0; } }