Submission #1102817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102817		uranium235	Mobile (BOI12_mobile)	Java	0 / 100	1072 ms	131072 KiB

mobile

//package ojuz;

import java.io.*;
import java.util.*;
import java.util.function.DoublePredicate;

public class mobile {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), l = Integer.parseInt(first[1]);

        Point[] ranges = new Point[n];
        for (int i = 0; i < n; i++) {
            first = reader.readLine().split(" ");
            ranges[i] = new Point(Integer.parseInt(first[0]), Integer.parseInt(first[1]));
        }

        double radius = firstTrue(1e-9, 1e10, d -> {
//            System.out.println("testing " + d);
            Queue<Double> queue = new PriorityQueue<>((a, b) -> {
                if (Math.abs(a) != Math.abs(b)) return Double.compare(Math.abs(a), Math.abs(b));
                return Double.compare(b, a);
            });
            for (Point r : ranges) {
                double left = r.x - Math.sqrt(d * d - r.y * r.y);
                if (Double.isNaN(left)) continue;
                queue.add(Math.max(left, 0));
                queue.add(-Math.min(r.x + r.x - left, l));
//                System.out.println("added " + (r.x + r.x - left));
            }

            if (queue.isEmpty() || queue.peek() != 0) return false;

            int in = 0;
            while (!queue.isEmpty()) {
                double val = queue.poll();
//                System.out.println("val " + val);
                if (val == -l) return true;

                if (val < 0) {
                    in--;
                    if (in == 0) return false;
                } else in++;
            }

            return true;
        });

        System.out.println(radius);
    }

    public static double firstTrue(double lo, double hi, DoublePredicate pred) {
        hi += Math.ulp(hi);
        double prevMid = -1;
        while (lo < hi) {
            double mid = lo + (hi - lo) / 2;
            if (Math.abs(mid - prevMid) < 1e-6) return lo;
            if (pred.test(mid)) hi = mid;
            else lo = mid + Math.ulp(mid);

            prevMid = mid;
        }
        return lo;
    }

    static class Point {
        public final int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

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