import java.io.*;
import java.util.*;
// class Balloons causes compilation error on ojuz
public class bal {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// number of balloonss
int n = Integer.parseInt(br.readLine());
// the radius of each balloon after inflating
double[] res = new double[n];
// the balloons we should check when we add a new one
Stack<Balloon> toCheck = new Stack<>();
// simulate inflating balloons
for (int i = 0; i < n; i++) {
// the x coordinate and the maximum radius of the current balloon being inflated
StringTokenizer st = new StringTokenizer(br.readLine());
long x = Integer.parseInt(st.nextToken());
double r = Integer.parseInt(st.nextToken());
// the maximum radius of the current balloon
double maxR = r;
/*
* as long as the stack is not empty, we want to check
* if the last balloon makes the radius of the current balloon smaller
*/
while (!toCheck.isEmpty()) {
// the radius if the current balloon touches the last balloon
double toLastR = toCheck.peek().calcR(x);
/*
* the maximum possible radius is the smaller one between current
* maximum and the maximum radius so that we touches the last balloon
* (by which we have to stop)
*/
maxR = Math.min(maxR, toLastR);
/*
* if current maximum radius >= radius of the last balloon, we can
* remove the last balloon since it will never be touched by any
* new balloons other than the current one
*/
if (maxR >= toCheck.peek().r) {
toCheck.pop();
// check the next balloon saved which will possibly reduce max_r
continue;
}
/*
* otherwise, the current balloon is smaller than the last saved balloon
* and we can stop checking
*/
else {
break;
}
}
/*
* save the x coordinate and radius of the current balloon, so that
* it can be checked later when a new balloon being inflated
*/
toCheck.add(new Balloon(x, maxR));
res[i] = maxR;
}
PrintWriter pw = new PrintWriter(System.out);
for (double r : res) {
pw.println(r);
}
pw.close();
}
// class to save the data of an infalted balloon
private static class Balloon {
public long x;
public double r;
public Balloon(long x, double r) {
this.x = x;
this.r = r;
}
/*
* how long can the radius of the new balloon at position bx be
* so that it touches the ballon a, which is described by
* its x position a.first and its radius a.second
*/
public double calcR(long bx) {
return (x - bx) * (x - bx) / (4 * r);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
8328 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
8144 KB |
2 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
8884 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
356 ms |
15460 KB |
2000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
756 ms |
18672 KB |
20000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1351 ms |
33620 KB |
50000 numbers |
| 2 |
Correct |
534 ms |
17364 KB |
49912 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1319 ms |
32352 KB |
100000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
954 ms |
26484 KB |
115362 numbers |
| 2 |
Correct |
634 ms |
18748 KB |
119971 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1067 ms |
25976 KB |
154271 numbers |
| 2 |
Correct |
629 ms |
21128 KB |
200000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1370 ms |
33936 KB |
200000 numbers |
| 2 |
Correct |
603 ms |
21292 KB |
199945 numbers |
