Submission #363992

#	Time	Username	Problem	Language	Result	Execution time	Memory
363992		bessie_the_cow	Mobile (BOI12_mobile)	Java	0 / 100	1101 ms	125196 KiB

mobile

//package 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 st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		
		ArrayList<Station> stations = new ArrayList<Station>();
		
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			stations.add(new Station(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		
		br.close();
		
		// binary search
		double min = 0;
		double max = Double.MAX_VALUE;
		
		while (max - min > 0.0001) {
			double mid = (min/2)+(max/2);
			if (works(stations, mid, L)) {
				max = mid;
			}
			else {
				min = mid;
			}
		}
		
		System.out.printf("%1.4f\n", min/2 + max/2);
		
	}
	
	public static boolean works(ArrayList<Station> stations, double radius, int L) {
		ArrayList<double[]> intervals = new ArrayList<double[]>();
		
		for (int i=0; i<stations.size(); i++) {
			double a = Math.sqrt(Math.pow(radius,2) - Math.pow(stations.get(i).y, 2));
			double start = stations.get(i).x-a;
			double end = stations.get(i).x+a;
			double[] curr = {start, end};
			intervals.add(curr);
		}
		
		Collections.sort(intervals, new Comparator<double[]>() {
			public int compare(double[] i1, double[] i2) {
				if (i1[0]-i2[0] < 0) {
					return -1;
				}
				else if (i1[0]-i2[0] > 0) {
					return 1;
				}
				else {
					return 0;
				}
			}
		});
		
		double prev = 0; // previous end time
		
		for (double[] interval: intervals) {
			if (interval[0] > prev) {
				return false;
			}
			prev = interval[1];
		}
		
		return prev >= L;
		
	}

}

class Station {
	int x;
	int y;
	
	public Station(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public String toString() {
		return "Station [x=" + x + ", y=" + y + "]";
	}
	
}

• 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