Submission #1140324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140324		sz_3312	Mobile (BOI12_mobile)	Java	12 / 100	776 ms	163100 KiB

mobile

import java.io.BufferedReader;
import java.io.InputStreamReader;
import static java.lang.Math.sqrt;
import static java.lang.Math.max;

public class mobile {

    /**
     * Checks if a given radius can cover all required points along the horizontal line of given length.
     *
     * @param radius the radius to check
     * @param x      the x-coordinates of the points
     * @param y      the y-coordinates of the points
     * @param length the total length to cover
     * @return true if the radius can cover the entire length, false otherwise
     */
    private static boolean canCoverAll(double radius, int[] x, int[] y, int length) {
        double endPoint = 0.0;
        for (int i = 0; i < x.length; i++) {
            if (y[i] > radius) {
                continue; // If the y-coordinate is greater than the radius, coverage is impossible.
            }
            double delta = sqrt(radius * radius - y[i] * y[i]);
            double right = x[i] + delta;
            if (x[i] - delta <= endPoint) {
                endPoint = max(endPoint, right);
            }
        }
        return endPoint >= length;
    }

    /**
     * Performs binary search to find the minimum radius required to cover the given length.
     *
     * @param x      the x-coordinates of the points
     * @param y      the y-coordinates of the points
     * @param length the total length to cover
     * @return the minimum radius with a precision of 1e-3
     */
    private static double findMinRadius(int[] x, int[] y, int length) {
        double lo = 1.0, hi = 1.5e9, epsilon = 1e-3;

        while (hi - lo > epsilon) {
            double mid = lo + (hi - lo) / 2;
            if (canCoverAll(mid, x, y, length)) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        return lo;
    }

    public static void main(String[] args) throws Exception {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            String[] input = reader.readLine().trim().split(" ");
            int pairCount = Integer.parseInt(input[0]);
            int length = Integer.parseInt(input[1]);

            int[] x = new int[pairCount];
            int[] y = new int[pairCount];
            for (int i = 0; i < pairCount; i++) {
                String[] position = reader.readLine().trim().split(" ");
                x[i] = Integer.parseInt(position[0]);
                y[i] = Integer.parseInt(position[1]);
            }

            double minRadius = findMinRadius(x, y, length);
            System.out.printf("%.4f%n", minRadius);
        }
    }
}

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