Submission #440218

#	Time	Username	Problem	Language	Result	Execution time	Memory
440218		ImaginaryIQ	Balloons (CEOI11_bal)	Java	50 / 100	2083 ms	33596 KiB

bal

import java.io.*;
import java.util.*;


public class bal {
    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;

        // standard input
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        // USACO-style file input
        public Kattio(String problemName) throws IOException {
            super(new FileWriter(problemName + ".out"));
            r = new BufferedReader(new FileReader(problemName + ".in"));
        }

        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }

        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }

    static int n;
    static pair [] arr;
    static double [] ans;
    static Stack<pair> stack = new Stack<>();

    public static void main(String[] args) throws IOException {
        Kattio io = new Kattio();
        n = io.nextInt();
        arr = new pair[n+1];
        ans = new double[n+1];

        arr[0] = new pair(0 , 0);
        for (int i = 1; i <= n; i++) {
            arr[i] = new pair(io.nextInt(), io.nextInt());
        }


        for (int i = 1; i <= n; i++) {
            pair minRad = arr[i];
            while((!stack.isEmpty())){
                    minRad.y = Math.min(minRad.y, calIntersect(minRad));
                    if(minRad.y >= stack.peek().y) {
                        stack.pop();
                    }else{
                        break;
                    }
            }
            ans[i] = minRad.y;
            stack.add(minRad);
        }


        for (int i = 1; i <= n; i++) {
            io.printf("%.3f", ans[i]);
            if(i == n)
                break;
            io.println();
        }
        io.close();
    }

    static double calIntersect(pair p1){
        return Math.pow(stack.peek().x - p1.x, 2) / (4 * stack.peek().y);
    }



    public static class pair {

        private final int x;
        private double y;

        public pair(final int x, final double y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(final Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof pair)) {
                return false;
            }

            final pair pair = (pair) o;

            if (x != pair.x) {
                return false;
            }
            if (y != pair.y) {
                return false;
            }

            return true;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + (int)y;
            return result;
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10