Submission #1139957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139957		sz_3312	Mobile (BOI12_mobile)	Java	50 / 100	1067 ms	196608 KiB

mobile

import java.io.BufferedReader;
import java.io.InputStreamReader;
import static java.lang.Math.sqrt;
import static java.lang.Math.max;
// Binary search with non-integers and geometry, special observation
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 pairs  the array of points (x, y)
     * @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[][] pairs, int length) {
        double endPoint = 0.0;
        for (long[] pair : pairs) {
            if (pair[1] > radius) {
                continue; // If the y-coordinate is greater than the radius, coverage is impossible.
            }
            double delta = sqrt(radius * radius - pair[1] * pair[1]);
            double left = pair[0] - delta;
            double right = pair[0] + delta;

            if (left <= endPoint) {
                endPoint = max(endPoint, right);
            }
        }
        return endPoint >= length;
    }

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

        while (hi - lo > epsilon) {
            double mid = lo + (hi - lo) / 2;
            if (canCoverAll(mid, pairs, 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]);

            long[][] pairs = new long[pairCount][2];
            for (int i = 0; i < pairCount; i++) {
                String[] position = reader.readLine().trim().split(" ");
                long x = Long.parseLong(position[0]);
                long y = Long.parseLong(position[1]);
                pairs[i] = new long[]{x, y};
            }

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

• 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