import java.io.*;
import java.util.*;
public class Balloons {
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);
}
}
}
Compilation message
bal.java:4: error: class Balloons is public, should be declared in a file named Balloons.java
public class Balloons {
^
1 error
