Submission #1278261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278261		QuantumPi	Mobile (BOI12_mobile)	Java	0 / 100	1102 ms	196608 KiB

mobile

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

public class mobile {
    public static int n, l;
    public static double[][] points;
    public static double alpha = 0.0001;
    public static void main(String[] args) throws IOException {
        BufferedReader fin = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader fin = new BufferedReader(new FileReader("G:\\My Drive\\USACO Problems\\Problems\\test.in"));
        PrintWriter fout = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(fin.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        points = new double[n][2];
        double low = 0.0;
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(fin.readLine());
            points[i][0] = Integer.parseInt(st.nextToken());
            points[i][1] = Integer.parseInt(st.nextToken());
            low = Math.max(low, Math.abs(points[i][1]));
        }
        //fout.println(Arrays.toString(findRange(2, 5)));
        double high = 1000000000005.0;
        while (!equal(low, high)) {
            double mid = (low+high)/2;
            //fout.println(mid);
            if (works(mid)) {
                high = mid;
            }
            else {
                low = mid+alpha;
            }
        }
        fout.println(low);

        fin.close();
        fout.close();
    }
    public static boolean equal(double a, double b) {
        return Math.abs(b-a) <= alpha;
    }
    public static boolean works(double r) {
        double[][] ranges = new double[n][2];
        for (int i=0; i<n; i++) {
            double[] d = findRange(i, r);
            ranges[i][0] = d[0];
            ranges[i][1] = d[1];
        }
        Arrays.sort(ranges, (double[] a, double[] b) -> Double.compare(a[0], b[0]));
        //System.out.println(Arrays.deepToString(ranges));
        for (int i=1; i<n; i++) {
            if (ranges[i][0] > ranges[i-1][1]) {
                return false;
            }
            ranges[i][0] = ranges[i-1][0];
            ranges[i][1] = Math.max(ranges[i-1][1], ranges[i][1]);
        }
        if (ranges[n-1][0] > 0 || ranges[n-1][1] < l) {
            return false;
        }
        return true;
    }
    public static double[] findRange(int i, double r) {
        double yDist = Math.abs(points[i][1]);
        double xDist = Math.sqrt(r*r-yDist*yDist);
        return new double[]{points[i][0]-xDist, points[i][0]+xDist};
    }
}

• 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