제출 #1140312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140312		sz_3312	Mobile (BOI12_mobile)	Java	12 / 100	860 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, int[][] pairs, int length) {
        double endPoint = 0.0;
        for (int[] 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(int[][] pairs, 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, 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]);

            int[][] pairs = new int[pairCount][2];
            for (int i = 0; i < pairCount; i++) {
                String[] position = reader.readLine().trim().split(" ");
                int x = Integer.parseInt(position[0]);
                int y = Integer.parseInt(position[1]);
                pairs[i] = new int[]{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: 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