# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1066685 | Oz121 | Balloons (CEOI11_bal) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.util.*;
public class Balloons {
public static void main(String[] args) throws IOException {
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer l1 = new StringTokenizer(scan.readLine()); int num = Integer.parseInt(l1.nextToken()); double[][] arr = new double[num][2];
for (int i = 0;i<num;i++) {
StringTokenizer st = new StringTokenizer(scan.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Stack<Integer> idx = new Stack<>(); double[] ans = new double[num];
for (int i = 0;i<num;i++) {
while (!idx.isEmpty()) {
int j = idx.peek();
double maxR = Math.pow(arr[i][0]-arr[j][0],2)/(4*ans[j]);
if (maxR>arr[i][1]) {
if (arr[i][1]<=arr[j][1]) {
idx.add(i); ans[i] = arr[i][1];
break;
}
else idx.pop();
} else { //maxR<=arr[i][1]
if (maxR<=arr[j][1]) {
idx.add(i); ans[i] = maxR;
break;
}
else idx.pop();
}
}
if (idx.isEmpty()) ans[i] = arr[i][1];
idx.add(i);
}
for (double i : ans) System.out.println(i+" ");
}
}