| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1139952 | sz_3312 | Mobile (BOI12_mobile) | Java | 0 ms | 0 KiB |
import java.io.BufferedReader;
import java.io.InputStreamReader;
import static java.lang.Math.sqrt;
import static java.lang.Math.max;
// Binary search with non-integers and geometry, special observation
public class Solution {
private static class Pair {
long x, y;
Pair(long x, long y) {
this.x = x;
this.y = y;
}
}
/**
* Checks if a given radius can cover all required points along the horizontal line of given length.
*
* @param radius the radius to check
* @param pairs the array of points (x, y)
* @param length the total length to cover
* @return true if the radius can cover the entire length, false otherwise
*/
private static boolean canCoverAll(double radius, Pair[] pairs, int length) {
double endPoint = 0.0;
for (Pair pair : pairs) {
if (pair.y > radius) {
continue; // If the y-coordinate is greater than the radius, coverage is impossible.
}
double delta = sqrt(radius * radius - pair.y * pair.y);
double left = pair.x - delta;
double right = pair.x + delta;
if (left <= endPoint) {
endPoint = max(endPoint, right);
}
}
return endPoint >= length;
}
/**
* Performs binary search to find the minimum radius required to cover the given length.
*
* @param pairs the array of points (x, y)
* @param length the total length to cover
* @return the minimum radius with a precision of 1e-3
*/
private static double findMinRadius(Pair[] pairs, int length) {
double lo = 1.0, hi = 1.5e9, epsilon = 1e-4;
while (hi - lo > epsilon) {
double mid = lo + (hi - lo) / 2;
if (canCoverAll(mid, pairs, length)) {
hi = mid;
} else {
lo = mid;
}
}
return lo;
}
public static void main(String[] args) throws Exception {
try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
String[] input = reader.readLine().trim().split(" ");
int pairCount = Integer.parseInt(input[0]);
int length = Integer.parseInt(input[1]);
Pair[] pairs = new Pair[pairCount];
for (int i = 0; i < pairCount; i++) {
String[] position = reader.readLine().trim().split(" ");
long x = Long.parseLong(position[0]);
long y = Long.parseLong(position[1]);
pairs[i] = new Pair(x, y);
}
double minRadius = findMinRadius(pairs, length);
System.out.printf("%.4f%n", minRadius);
}
}
}