Submission #1254796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254796		franktastic	Mobile (BOI12_mobile)	Java	26 / 100	1099 ms	64152 KiB

mobile

import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.*;

public class mobile { 
    static FastIO io = new FastIO();

    public static void main(String[] args) throws Exception {
        int n = io.nextInt();
        int L = io.nextInt();
        var x = new int[n];
        var y = new int[n];
        for (int i=0; i<n; i++) {
            x[i] = io.nextInt();
            y[i] = Math.abs(io.nextInt());
        }

        double lo = 0;
        double hi = 3e9;
        for (int i=0; i<45; i++) {
            double mid = (lo+hi)/2;
            boolean v = isValid(mid, x, y, L);
            //System.out.println("trying: " + mid + ", res = " + v);
            if (v) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        io.out.println((lo+hi)/2);
    }

    static double[][] segments = new double[1000000][2];

    static boolean isValid(double r, int[] x, int[] y, int L) {
        int n = x.length;
        int len = 0;
        for (int i=0; i<n; i++) {
            if (y[i] > r) {
                continue;
            }
            double disc = Math.sqrt(r*r - 1L * y[i]*y[i]);
            segments[len][0] = x[i] - disc;
            segments[len++][1] = x[i] + disc;
        }
        if (len == 0) {
            return false;
        }
        Arrays.sort(segments, 0, len, (a,b) -> Double.compare(a[0], b[0]));


        // check that the whole line is covered 
        double end = 0;
        for (double[] i : segments) {
            if (end >= L) {
                break;
            }
            if (end < i[0]) {
                return false;
            }
            end = Math.max(end, i[1]);
        }
        return true;
    }




























    // ==================================================================
    // ======================== Boilerplate Code v2.1 ===================
    // ==================================================================
    static class FastIO {
        private static final int BUF_SIZE = 1 << 20;
        private final InputStream in;
        public final PrintWriter out;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr = 0, buflen = 0;
        private final StringBuilder sb = new StringBuilder(BUF_SIZE);

        public FastIO() { // default to stdin/stdout
            in = System.in;
            out = new PrintWriter(new BufferedOutputStream(System.out, BUF_SIZE),true); 
            // Note: autoFlushing on newlines can be disabled for better perf, just remember to manually flush yourself!!
        }

        public FastIO(String inputFile, String outputFile) {
            try {
                in  = new FileInputStream(inputFile);
                out = new PrintWriter(new BufferedOutputStream(new FileOutputStream(outputFile), BUF_SIZE), true);
            } catch (IOException e) { throw new UncheckedIOException(e); }
        }

        private byte read() throws IOException {
            if (ptr >= buflen) {
                buflen = in.read(buf, 0, BUF_SIZE);
                ptr = 0;
                if (buflen == -1) return -1;
            }
            return buf[ptr++];
        }

        public int nextInt() throws IOException {
            byte b; do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) throw new IOException("End of input");
            boolean neg = (b == '-'); if (neg) b = read();
            int x = 0;
            while (b >= '0' && b <= '9') {
                x = x * 10 + (b - '0');
                b = read();
            }
            return neg ? -x : x;
        }

        public long nextLong() throws IOException {
            byte b; do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) throw new IOException("End of input");
            boolean neg = (b == '-'); if (neg) b = read();
            long x = 0;
            while (b >= '0' && b <= '9') {
                x = x * 10 + (b - '0');
                b = read();
            }
            return neg ? -x : x;
        }

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public char nextChar() throws IOException {
            byte b; do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) throw new IOException("End of input");
            return (char) b;
        }

        public String next() throws IOException {
            byte b; do { b = read(); } while (b != -1 && b <= ' ');
            if (b == -1) return null;
            sb.setLength(0);
            do {
                sb.append((char) b);
                b = read();
            } while (b != -1 && b > ' ');
            return sb.toString();
        }

        public String nextLine() throws IOException {
            StringBuilder line = new StringBuilder();
            byte b;
            while ((b = read()) != -1 && b != '\n') {
                if (b != '\r') line.append((char) b);
            }
            return line.toString();
        }

        public int[] nextArrayInt(int n) throws IOException { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; }
        public long[] nextArrayLong(int n) throws IOException { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; }
        public double[] nextArrayDouble(int n) throws IOException { double[] a = new double[n]; for (int i = 0; i < n; i++) a[i] = nextDouble(); return a; }
        public String[] nextArrayString(int n) throws IOException { String[] a = new String[n]; for (int i = 0; i < n; i++) a[i] = next(); return a; }
    }

    static long gcd(long x, long y) {
        x = Math.abs(x); y = Math.abs(y);
        while (y != 0) {
            long c = x % y;
            x = y;
            y = c;
        }
        return x;
    }

    public static int gcd(int x, int y) {
        x = Math.abs(x); y = Math.abs(y);
        while (y != 0) {
            int c = x % y;
            x = y;
            y = c;
        }
        return x;
    }
    
    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    public static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    // Returns the next permutation of [start, end) in ascending. 
    // Will return false when there are none left. Can handle duplicates just fine.
    public static boolean nextPermutation(int[] nums, int start, int end) { 
        for (int i=end-2; i>=start; i--) {
            if (nums[i] < nums[i+1]) {
                int replacement = nums[i+1]; 
                int replacementIndex = i+1;
                for (int j=i+2; j<end; j++) {
                    if (nums[j] > nums[i] && nums[j] <= replacement) {
                        replacement = nums[j];
                        replacementIndex = j;
                    }
                }
                swap(nums, i, replacementIndex);
                reverse(nums, i+1, end);  // sort the tail, which is conveniently reversed
                return true;
            }
        }
        return false;
    }

    public static void reverse(int[] nums, int start, int end) { // swaps [start, end)
        end--;
        while (start < end) {
            swap(nums, start, end);
            start++; 
            end--;
        }
    }
    
    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // Fisher-Yates shuffle algorithm - Can be used to avoid quicksort's O(N^2) worst case
    public static void arrayShuffle(int[] arr) { 
        Random r = new Random();
        for (int i=arr.length-1; i>=1; i--) {
            int inx = r.nextInt(i+1);
            int t = arr[inx];
            arr[inx] = arr[i];
            arr[i] = t;
        }
    }

    public static void arrayShuffle(long[] arr) { 
        Random r = new Random();
        for (int i=arr.length-1; i>=1; i--) {
            int inx = r.nextInt(i+1);
            long t = arr[inx];
            arr[inx] = arr[i];
            arr[i] = t;
        }
    }

    public static void arrayShuffle(double[] arr) { 
        Random r = new Random();
        for (int i=arr.length-1; i>=1; i--) {
            int inx = r.nextInt(i+1);
            double t = arr[inx];
            arr[inx] = arr[i];
            arr[i] = t;
        }
    }

    static long modpow(long a, long b, long mod) { // a^b % mod (note: 0^0 returns 1)
        a %= mod;
        long ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                ans = (ans * a) % mod;
            }
            b >>= 1;
            a = a * a % mod;
        }
        return ans;
    }

    // WARNING: Only works for prime MOD. 
    public static long modInverse(long a, long mod) {  
        return modpow(a, mod-2, mod); // fermat's little theorem a^(p-1) = 1(mod p)
    }

    public static int[][] buildGraph(int n, int[][] edges, boolean bidirectional) { // fast adj list builder
        var g = new int[n][];
        int[] outDegree = new int[n];
        for (int[] e : edges) {
            outDegree[e[0]]++;
            if (bidirectional) {
                outDegree[e[1]]++;
            }
        }
        for (int i=0; i<n; i++) {
            g[i] = new int[outDegree[i]];
        }
        for (int[] e : edges) {
            int u = e[0];
            int v = e[1];
            g[u][--outDegree[u]] = v;
            if (bidirectional) {
                g[v][--outDegree[v]] = u;
            }
        }
        return g;
    }

    public static int[] concat(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static long[] concat(long[] a, long[] b) {
        long[] result = new long[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static String[] concat(String[] a, String[] b) {
        String[] result = new String[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static double[] concat(double[] a, double[] b) {
        double[] result = new double[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }
    
    public static char[] concat(char[] a, char[] b) {
        char[] result = new char[a.length + b.length];
        System.arraycopy(a, 0, result, 0, a.length);
        System.arraycopy(b, 0, result, a.length, b.length);
        return result;
    }

    public static int min(int... x) { // Assumes non-zero arguments
        int m = x[0];
        for (int v : x) m = v < m ? v : m;
        return m;
    }

    public static long min(long... x) { // Assumes non-zero arguments
        long m = x[0];
        for (long v : x) m = v < m ? v : m;
        return m;
    }

    public static double min(double... x) { // Assumes non-zero arguments
        double m = x[0];
        for (double v : x) m = v < m ? v : m;
        return m;
    }

    public static char min(char... x) { // Assumes non-zero arguments
        char m = x[0];
        for (char v : x) m = v < m ? v : m;
        return m;
    }

    public static String min(String... x) { // Assumes non-zero arguments
        String m = x[0];
        for (String xx : x) {
            if (m.compareTo(xx) > 0) {
                m = xx;
            }
        }
        return m;
    }

    public static int max(int... x) { // Assumes non-zero arguments
        int m = x[0];
        for (int v : x)  m = v > m ? v : m;
        return m;
    }

    public static long max(long... x) { // Assumes non-zero arguments
        long m = x[0];
        for (long v : x)  m = v > m ? v : m;
        return m;
    }

    public static double max(double... x) { // Assumes non-zero arguments
        double m = x[0];
        for (double v : x)  m = v > m ? v : m;
        return m;
    }

    public static char max(char... x) { // Assumes non-zero arguments
        char m = x[0];
        for (char v : x)  m = v > m ? v : m;
        return m;
    }

    public static String max(String... x) { // Assumes non-zero arguments
        String m = x[0];
        for (String xx : x) {
            if (m.compareTo(xx) < 0) {
                m = xx;
            }
        }
        return m;
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5