Untitled
unknown
plain_text
a month ago
2.4 kB
1
Indexable
Never
import java.util.*; class FrogJumps { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int caseNumber = 1; caseNumber <= t; caseNumber++) { int n = scanner.nextInt(); int[][] leaves = new int[n][3]; for (int i = 0; i < n; i++) { for (int j = 0; j < 3; j++) { leaves[i][j] = scanner.nextInt(); } } int[] result = frogJumps(n, leaves); System.out.println(result[0] + " " + result[1]); } } static int[] frogJumps(int n, int[][] leaves) { int[][] distances = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { distances[i][j] = 0; } else { int dist = calculateDistance(leaves[i], leaves[j]); if (dist <= 40) { distances[i][j] = 0; } else if (dist <= 90) { distances[i][j] = 1; } } } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]); } } } int minJumps = Integer.MAX_VALUE; int shortJumps = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (distances[0][i] + distances[i][j] + distances[j][n - 1] == distances[0][n - 1]) { int totalJumps = distances[i][j]; shortJumps = Math.min(shortJumps, distances[0][i]); minJumps = Math.min(minJumps, totalJumps); } } } if (minJumps == Integer.MAX_VALUE) { return new int[]{-1, -1}; } else { return new int[]{minJumps, shortJumps}; } } static int calculateDistance(int[] leaf1, int[] leaf2) { int x1 = leaf1[0]; int y1 = leaf1[1]; int x2 = leaf2[0]; int y2 = leaf2[1]; return (int) Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } }