Untitled
unknown
plain_text
2 years ago
2.5 kB
6
Indexable
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;
}
}
Editor is loading...