import java.io.*;
import java.util.*;
public class mobile {
static int N;
static int L;
static ArrayList<Coordinate> coordinates;
public static void main(String[] args) throws IOException {
BufferedReader br;
PrintWriter out;
StringTokenizer st;
try {
br = new BufferedReader(new FileReader("highcard.in"));
out = new PrintWriter(new BufferedWriter(new FileWriter("highcard.out")));
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
st = new StringTokenizer(br.readLine());
}
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
coordinates = new ArrayList<>();
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
coordinates.add(new Coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
double left = 0;
double right = 1500000000;
double answer = 0;
do {
// System.out.println(left + " " + right);
double mid = (left + right) / 2;
boolean working = works(mid);
if (working) {
answer = mid;
left = mid;
} else {
right = mid;
}
} while (Math.abs(left - right) > 0.0001);
out.print(answer);
out.close();
}
static boolean works(double radius) {
ArrayList<Intercept> intercepts = new ArrayList<>();
int id = 0;
for(Coordinate c : coordinates) {
double[] theseInter = getIntercepts(c.x, c.y, radius);
if(theseInter.length == 2) {
intercepts.add(new Intercept(Math.min(theseInter[0], theseInter[1]), 1, id));
intercepts.add(new Intercept(Math.max(theseInter[0], theseInter[1]), 2, id));
id++;
} else if (theseInter.length == 1) {
intercepts.add(new Intercept(theseInter[0], 0, id));
id++;
}
}
intercepts.sort(new Compare());
int numCircles = 0;
for (Intercept intercept : intercepts) {
if (intercept.x >= 0 && intercept.x <= L) {
if(numCircles == 0 || (numCircles == 1 && intercept.type == 2)) {
return true;
}
}
if (intercept.type == 1) {
numCircles++;
} else if (intercept.type == 2) {
numCircles--;
}
}
return intercepts.size() == 0;
}
static double[] getIntercepts(double h, double k, double radius) {
if(radius * radius - k * k > 0) {
double sqrt = Math.sqrt(radius * radius - k * k);
return new double[] {sqrt + h, -sqrt + h};
} else if (radius * radius - k * k == 0) {
return new double[] {h};
} else {
return new double[] {};
}
}
static class Coordinate {
int x;
int y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Intercept {
double x;
int type;
int id;
public Intercept(double x, int t, int id) {
this.x = x;
type = t;
this.id = id;
}
}
static class Compare implements Comparator<Intercept> {
@Override
public int compare(Intercept o1, Intercept o2) {
if(o1.x < o2.x) {
return -1;
} else if (o1.x == o2.x) {
return 0;
}
return 1;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
8600 KB |
Output is correct |
| 2 |
Correct |
66 ms |
8608 KB |
Output is correct |
| 3 |
Correct |
66 ms |
8532 KB |
Output is correct |
| 4 |
Correct |
63 ms |
8448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
12260 KB |
Output is correct |
| 2 |
Correct |
118 ms |
12096 KB |
Output is correct |
| 3 |
Correct |
137 ms |
12600 KB |
Output is correct |
| 4 |
Correct |
141 ms |
12636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
437 ms |
14924 KB |
Output is correct |
| 2 |
Correct |
601 ms |
15244 KB |
Output is correct |
| 3 |
Correct |
395 ms |
15244 KB |
Output is correct |
| 4 |
Correct |
594 ms |
15484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
592 ms |
15676 KB |
Output is correct |
| 2 |
Correct |
444 ms |
15312 KB |
Output is correct |
| 3 |
Correct |
866 ms |
16108 KB |
Output is correct |
| 4 |
Correct |
621 ms |
15776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
671 ms |
15584 KB |
Output is correct |
| 2 |
Correct |
459 ms |
15336 KB |
Output is correct |
| 3 |
Correct |
718 ms |
15672 KB |
Output is correct |
| 4 |
Correct |
524 ms |
15704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
713 ms |
15728 KB |
Output is correct |
| 2 |
Correct |
494 ms |
15216 KB |
Output is correct |
| 3 |
Correct |
857 ms |
15784 KB |
Output is correct |
| 4 |
Correct |
569 ms |
15476 KB |
Output is correct |
| 5 |
Correct |
572 ms |
15860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
35580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1066 ms |
36948 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
39824 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
41644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1050 ms |
29920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
89076 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
85960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
916 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
77744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
120416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
102904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1006 ms |
131072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
120268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
131072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1054 ms |
131072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
