oj.uz

Submission #363987

# Submission time Handle Problem Language Result Execution time Memory
363987 2021-02-07T20:48:10 Z bessie_the_cow Mobile (BOI12_mobile) Java 11
0 / 100
 1000 ms 126316 KB 
//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+max)/2;
			if (works(stations, mid, L)) {
				max = mid;
			}
			else {
				min = mid;
			}
		}
		
		System.out.println((min+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.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 11376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 162 ms 13232 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 503 ms 15352 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 655 ms 15216 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 614 ms 15380 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 14828 KB Output is correct
2 Correct 535 ms 14684 KB Output is correct
3 Incorrect 634 ms 15564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 25836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 27132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 27352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 28968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 29756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 96432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 91340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 114776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 86836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 123564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1102 ms 118800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 126316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 112528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 112144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1102 ms 110252 KB Time limit exceeded
2 Halted 0 ms 0 KB -