| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 480698 | 2021-10-17T22:07:29 Z | Toinfinity1 | Balloons (CEOI11_bal) | Java 11 | 0 ms | 0 KB |
import java.io.*;
import java.util.*;
public class Main
{
static class InputReader {
BufferedReader reader;
StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
String next() { // reads in the next string
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() { // reads in the next int
return Integer.parseInt(next());
}
public long nextLong() { // reads in the next long
return Long.parseLong(next());
}
public double nextDouble() { // reads in the next double
return Double.parseDouble(next());
}
}
static InputReader r = new InputReader(System.in);
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)
{
int n = r.nextInt();
double[] rad = new double[n];
double[] x = new double[n];
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < n; i ++)
{
double a = r.nextDouble();
double b = r.nextDouble();
double last = 0.0;
while (!stack.isEmpty() && (rad[stack.peek()] <= b || last <= b))
{
double ra = rad[stack.peek()];
double lo = x[stack.peek()];
b = Math.min(b, ((a-lo)*(a-lo))/(4*ra));
last = ra;
if (b >= ra)
{
stack.pop();
}
}
x[i] = a;
rad[i] = b;
stack.add(i);
}
pw.println(Arrays.toString(rad));
pw.close();
}
}