Submission #605824

#	Time	Username	Problem	Language	Result	Execution time	Memory
605824		bzhu524	Mobile (BOI12_mobile)	Java	95 / 100	1042 ms	85784 KiB

mobile

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


public class mobile {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer l1 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(l1.nextToken());
        int len = Integer.parseInt(l1.nextToken());
        Point[] points = new Point[n];
        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            points[i] = new Point(x, y);
        }

        double lower = 1;
        double upper = 1000000000;
        
        while (upper - lower > 1e-3) {
            double mid = (upper + lower) / 2;
            double currPoint = 0;
            for (int i=0; i<n; i++) { // remove this loop for faster solution
                long x = points[i].x;
                long y = points[i].y;

                double delta = Math.sqrt(mid * mid - y * y);
                double p1 = x - delta;
                double p2 = x + delta;

                if (p1 <= currPoint) {
                    currPoint = Math.max(currPoint, p2);
                }
            }
            if (currPoint < len) {
                lower = mid;
            } else {
                upper = mid;
            }
        }

        String r = String.format("%.6f", lower);
        System.out.println(r);
    }

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

• 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: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 0 / 5