Submission #1278271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278271		QuantumPi	Mobile (BOI12_mobile)	Java	25 / 100	780 ms	196608 KiB

mobile

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

public class mobile {
    public static int n, l;
    public static double[][] points;
    public static double alpha = 0.0001;
    public static void main(String[] args) throws IOException {
        BufferedReader fin = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader fin = new BufferedReader(new FileReader("G:\\My Drive\\USACO Problems\\Problems\\test.in"));
        PrintWriter fout = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(fin.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        points = new double[n][2];
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(fin.readLine());
            points[i][0] = Integer.parseInt(st.nextToken());
            points[i][1] = Integer.parseInt(st.nextToken());
        }
        //fout.println(Arrays.toString(findRange(2, 5)));
        double low = 0.0;
        double high = 1e14+5;
        for (int i=0; i<80; i++) {
            double mid = (low+high)/2;
            //fout.println(mid);
            if (works(mid)) {
                high = mid;
            }
            else {
                low = mid+alpha;
            }
        }
        fout.printf("%.5f%n", low);

        fin.close();
        fout.close();
    }
    public static boolean works(double r) {
        final double EPS = 1e-12;
        List<double[]> ranges = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            double[] d = findRange(i, r); 
            if (Double.isNaN(d[0]) || Double.isNaN(d[1])) continue;

            double left = Math.max(0.0, d[0]);
            double right = Math.min(l, d[1]);
            if (left <= right) ranges.add(new double[]{left, right});
        }

        int m = ranges.size();
        if (m == 0) return false;

        ranges.sort(Comparator.comparingDouble(a -> a[0]));

        double curL = ranges.get(0)[0];
        double curR = ranges.get(0)[1];

        if (curL > 0.0 + EPS) return false;
        if (curR >= l - EPS) return true;

        for (int i = 1; i < m; i++) {
            double nextL = ranges.get(i)[0];
            double nextR = ranges.get(i)[1];

            if (nextL > curR + EPS) return false;
            if (nextR > curR) curR = nextR;

            if (curR >= l - EPS) return true;
        }

        return curR >= l - EPS;
    }
    public static double[] findRange(int i, double r) {
        double yDist = Math.abs(points[i][1]);
        double xDist = Math.sqrt(r*r-yDist*yDist);
        return new double[]{points[i][0]-xDist, points[i][0]+xDist};
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 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