Untitled
unknown
plain_text
a month ago
2.5 kB
1
Indexable
Never
import java.util.*; import java.util.stream.Collectors; class Node { int x, y, r; public Node(int x, int y, int r) { this.x = x; this.y = y; this.r = r; } } public class FrogJump { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int t = 0; t < T; t++) { int n = sc.nextInt(); Node[] nodes = new Node[n]; for (int i = 0; i < n; i++) { int x = sc.nextInt(); int y = sc.nextInt(); int r = sc.nextInt(); nodes[i] = new Node(x, y, r); } int[][] dp = new int[n][2]; for (int i = 0; i < n; i++) { dp[i][0] = dp[i][1] = Integer.MAX_VALUE - 1; if (nodes[i].y - nodes[i].r <= 0) { dp[i][0] = 0; dp[i][1] = 1; } for (int j = 0; j < i; j++) { int distance = calculateDistance(nodes[i], nodes[j]); if (distance <= 40) { if (dp[j][0] != Integer.MAX_VALUE - 1 && dp[j][0] + 1 < dp[i][0]) { dp[i][0] = dp[j][0] + 1; dp[i][1] = dp[j][1]; } } else if (distance <= 90) { if (dp[j][0] != Integer.MAX_VALUE - 1 && dp[j][0] < dp[i][0]) { dp[i][0] = dp[j][0]; dp[i][1] = dp[j][1] + 1; } } } } int minJumps = Integer.MAX_VALUE; int minGaps = -1; for (int i = 0; i < n; i++) { if (nodes[i].y + nodes[i].r >= 100) { if (dp[i][0] != Integer.MAX_VALUE - 1 && dp[i][1] < minGaps) { minGaps = dp[i][1]; minJumps = dp[i][0]; } } } if (minJumps == Integer.MAX_VALUE - 1) { System.out.println("-1"); } else { System.out.println(minJumps + " " + minGaps); } } } static int calculateDistance(Node a, Node b) { int dx = a.x - b.x; int dy = a.y - b.y; return (int) Math.sqrt(dx * dx + dy * dy) - a.r - b.r; } }