oj.uz

Submission #440217

# Submission time Handle Problem Language Result Execution time Memory
440217 2021-07-01T18:53:46 Z ImaginaryIQ Balloons (CEOI11_bal) Java 11
10 / 100
 2000 ms 36340 KB 
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()) && check(arr[i])){
                if(check(arr[i])){
                    // mark the touching radius
                    minRad.y = Math.min(minRad.y, calIntersect(minRad));
                    stack.pop();
                }
            }
            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);
    }

    static boolean check(pair p1){ // check if the circle intersects
        double x1 = p1.x, y1 = p1.y, x2 = stack.peek().x, y2 = stack.peek().y, r1 = p1.y, r2 = stack.peek().y;
        double distSq = (x1 - x2) * (x1 - x2) +
                (y1 - y2) * (y1 - y2);
        double radSumSq = (r1 + r2) * (r1 + r2);
        if (distSq == radSumSq)
            return false;
        else if (distSq > radSumSq)
            return false;
        else
            return true;
    }

    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 9808 KB 5th numbers differ - expected: '17.1630000000', found: '99.0000000000', error = '81.8370000000'

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 9568 KB 2 numbers

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 173 ms 10212 KB 3rd numbers differ - expected: '0.0420000000', found: '3.0000000000', error = '2.9580000000'

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 720 ms 19232 KB 114th numbers differ - expected: '39.0180000000', found: '56.0000000000', error = '16.9820000000'

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1725 ms 23048 KB 196th numbers differ - expected: '100.7250000000', found: '111.0000000000', error = '10.2750000000'

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 31708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 29228 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1958 ms 29732 KB 4645th numbers differ - expected: '0.0260000000', found: '8.0000000000', error = '7.9740000000'
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 34368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 36340 KB Time limit exceeded
2 Halted 0 ms 0 KB -