Submission #480701

#TimeUsernameProblemLanguageResultExecution timeMemory
480701Toinfinity1Balloons (CEOI11_bal)Java
100 / 100
1617 ms35464 KiB
import java.io.*; import java.util.*; public class bal { 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); } for (int i = 0; i < n; i ++) { pw.println(rad[i]); } pw.close(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...