oj.uz

답안 #363986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363986 2021-02-07T20:45:44 Z bessie_the_cow Mobile (BOI12_mobile) Java 11
0 / 100
 1000 ms 131072 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)) {
				max = mid;
			}
			else {
				min = mid;
			}
		}
		
		System.out.println((min+max)/2);
	}
	
	public static boolean works(ArrayList<Station> stations, double radius) {
		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 true;
		
	}

}

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 127 ms 11764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 163 ms 13064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 509 ms 15116 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 660 ms 15248 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 611 ms 15356 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 543 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 27596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1071 ms 27668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1079 ms 28000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1049 ms 30732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1092 ms 31364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1101 ms 100540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1056 ms 99484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1069 ms 105620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 106028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 129464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 130416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1102 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 125572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1090 ms 120608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1096 ms 126768 KB Time limit exceeded
2 Halted 0 ms 0 KB -