Submission #1207778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207778		sosuke	Mobile (BOI12_mobile)	Java	0 / 100	1103 ms	175492 KiB

mobile

import java.util.*;

public class mobile {
    static class Point {
        double x, y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }

    /**
     * @return the intersection of the perpendicular line that
     * crosses the midpoint of Points a & b with the highway
     */
    static double maxPoint(Point a, Point b) {
        return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * b.x - 2 * a.x);
    }

    /** @return the euclidean distance between points a & b */
    static double dist(Point a, Point b) {
        return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();

        Deque<Point> needed = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            Point cur = new Point(sc.nextDouble(), Math.abs(sc.nextDouble()));

            // Always take the one with the lowest y coordinate
            if (!needed.isEmpty() && needed.getLast().x == cur.x) {
                if (cur.y >= needed.getLast().y) {
                    continue;
                } else {
                    needed.removeLast();
                }
            }

            // Find "crosses"
            while (needed.size() > 1) {
                Point last = needed.getLast();
                Point secondLast = needed.removeLast(); // Remove last to access the new last
                if (maxPoint(secondLast, last) > maxPoint(last, cur)) {
                    // Keep removing if the intersection condition is met
                } else {
                    needed.addLast(secondLast); // Re-add if condition fails
                    break;
                }
            }

            needed.addLast(cur);
        }

        // Remove out-of-bounds points from the start
        while (needed.size() > 1 && maxPoint(needed.getFirst(), needed.getFirst()) < 0) {
            needed.removeFirst();
        }

        // Remove out-of-bounds points from the end
        while (needed.size() > 1 && maxPoint(needed.getLast(), needed.getLast()) > l) {
            needed.removeLast();
        }

        // Convert Deque to List for index-based access
        List<Point> listNeeded = new ArrayList<>(needed);
        double ans = 0;
        for (int x = 0; x < listNeeded.size(); x++) {
            Point left = new Point(0, 0);
            Point right = new Point(l, 0);

            if (x > 0) {
                left.x = maxPoint(listNeeded.get(x), listNeeded.get(x - 1));
            }
            if (x < listNeeded.size() - 1) {
                right.x = maxPoint(listNeeded.get(x), listNeeded.get(x + 1));
            }

            if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) {
                continue;
            }

            ans = Math.max(ans, Math.max(dist(listNeeded.get(x), left), dist(listNeeded.get(x), right)));
        }

        System.out.printf("%.8f\n", ans);
    }
}

• 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