Submission #1140328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140328		sz_3312	Mobile (BOI12_mobile)	Java	50 / 100	805 ms	186676 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 coordinates the x and y coordinates of points, stored in a single array
     * @param pairCount the number of 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, long[] coordinates, int pairCount, int length) {
        double endPoint = 0.0;
        for (int i = 0; i < pairCount; i++) {
            long x = coordinates[2 * i];
            long y = coordinates[2 * i + 1];
            if (y > radius) {
                continue; // If the y-coordinate is greater than the radius, coverage is impossible.
            }
            double delta = sqrt(radius * radius - y * y);
            double right = x + delta;
            if (x - delta <= endPoint) {
                endPoint = max(endPoint, right);
            }
        }
        return endPoint >= length;
    }

    /**
     * Performs binary search to find the minimum radius required to cover the given length.
     *
     * @param coordinates the x and y coordinates of points, stored in a single array
     * @param pairCount the number of points
     * @param length the total length to cover
     * @return the minimum radius with a precision of 1e-3
     */
    private static double findMinRadius(long[] coordinates, int pairCount, 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, coordinates, pairCount, 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]);

            // Use a single array to store both x and y coordinates
            long[] coordinates = new long[pairCount * 2];
            for (int i = 0; i < pairCount; i++) {
                String[] position = reader.readLine().trim().split(" ");
                coordinates[2 * i] = Long.parseLong(position[0]);
                coordinates[2 * i + 1] = Long.parseLong(position[1]);
            }

            System.out.printf("%.4f%n", findMinRadius(coordinates, pairCount, length));
        }
    }
}

• 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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 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