# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
746196 | rahulverma | Balloons (CEOI11_bal) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
public class balloons {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] coord = new int[n];
int[] maxRad = new int[n];
double[] ans = new double[n];
for(int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
coord[i] = Integer.parseInt(st.nextToken());
maxRad[i] = Integer.parseInt(st.nextToken());
}
ans[0] = maxRad[0];
Stack<Integer> stack = new Stack<Integer>();
stack.add(0); // indexes in the stack
for(int i = 1; i < n; i++) {
double pos = maxRad[i];
while(!stack.isEmpty()) {
int top = stack.peek();
double distance = dist(coord[top], ans[top], coord[i]);
if(distance < maxRad[i]) {
stack.pop();
pos = distance;
}
else {
pos = maxRad[i];
break;
}
}
ans[i] = pos;
stack.add(i);
}
for(int i = 0; i < n; i++) {
System.out.format("%.3f", (round(ans[i], 3)));
System.out.println();
}
}
public static double dist(int x1, double r1, int x2) {
double x_1 = x1;
double x_2 = x2;
return (x_1 - x_2) * (x_1 - x_2) / (4*r1);
}
private static double round(double value, int places) {
if (places < 0) throw new IllegalArgumentException();
BigDecimal bd = new BigDecimal(Double.toString(value));
bd = bd.setScale(places, RoundingMode.HALF_UP);
return bd.doubleValue();
}
}