Submission #1132077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132077		mrsmartypants	Mobile (BOI12_mobile)	Java	40 / 100	1102 ms	183684 KiB

mobile

import java.awt.*;
import java.io.*;
import java.util.*;

public class mobile {

    static class Point {
        double x, y;

        public Point() {
        }

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

    static double criticalPoint(Point a, Point b) {
        return (a.x*a.x - b.x*b.x + a.y*a.y - b.y*b.y) / (2*(a.x-b.x));
    }

    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) throws IOException {

//        BufferedReader reader = new BufferedReader(new FileReader("input.in"));
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        LinkedList<Point> needed = new LinkedList<>(); // Java Queues don't have indices so we will use ArrayList and 2P
        // this should already be sorted

        for (int i = 0; i < N; i++) {
            Point cur = new Point();
            st = new StringTokenizer(reader.readLine());
            cur.x = Integer.parseInt(st.nextToken());
            cur.y = Integer.parseInt(st.nextToken());
            if (cur.y < 0) cur.y = -cur.y; // negative y and positive y are treated the same. you can use the orthocenter to prove this.

            if (needed.size() > 0 && needed.peekLast().x == cur.x) { // if x coord is the same remove farther away y-coord points.
                if (cur.y >= needed.peekLast().y) {
                    continue;
                } else if (cur.y < needed.peekLast().y) {
                    needed.removeLast();
                }
            }

            // find crosses
            while ( needed.size() > 1 && criticalPoint(needed.get(needed.size() - 2), needed.peekLast()) >
                    criticalPoint(needed.peekLast(), cur)) {
                needed.removeLast();
            }

            needed.addLast(cur);

        }

        while (needed.size() > 1 && criticalPoint(needed.get(0), needed.get(1)) < 0) {
            needed.removeFirst();
        }

        while (needed.size() > 1 && criticalPoint(needed.get(needed.size() - 2), needed.peekLast()) > L) {
            needed.removeLast();
        } // remove out of bounds points. but must keep at least one.


        double ans = 0;
        for (int x = 0; x < needed.size(); x++) {
            Point left = new Point(0, 0);
            Point right = new Point(L, 0);

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

            if (left.x < 0 || right.x > L || right.x < 0 || left.x > L) continue;

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

        writer.println(ans);
        writer.close();
    }
}

• 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: 0 / 5
• Subtask 10: 5 / 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