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());
int 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;
}
for (double r : res) {
System.out.println(r);
}
}
// class to save the data of an infalted balloon
private static class Balloon {
public int x;
public double r;
public Balloon(int 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(int bx) {
return (x - bx) * (x - bx) / (4 * r);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
8716 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
8508 KB |
2nd numbers differ - expected: '252735385.4379999936', found: '0.9334151241', error = '252735384.5045848787' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
8916 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
508 ms |
23668 KB |
506th numbers differ - expected: '365.0000000000', found: '-2481854.0646065245', error = '2482219.0646065245' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1242 ms |
28836 KB |
655th numbers differ - expected: '591.0000000000', found: '-2402336.3030539569', error = '2402927.3030539569' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1324 ms |
22164 KB |
4th numbers differ - expected: '15396.0000000000', found: '-8148.5509720554', error = '23544.5509720554' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1979 ms |
33140 KB |
7234th numbers differ - expected: '7160.0000000000', found: '-2398141.9988687783', error = '2405301.9988687783' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1848 ms |
26788 KB |
4643rd numbers differ - expected: '2427.0000000000', found: '-2355611.7017843765', error = '2358038.7017843765' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
27448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
34164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
