| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1207503 | sosuke | Mobile (BOI12_mobile) | Java | 0 ms | 0 KiB |
import java.util.*;
public class mobile {
static class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
/**
* @return the intersection of the perpendicular line that
* crosses the midpoint of Points a & b with the highway
*/
static double maxPoint(Point a, Point b) {
return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * b.x - 2 * a.x);
}
/** @return the euclidean distance between points a & b */
static double dist(Point a, Point b) {
return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int l = sc.nextInt();
Deque<Point> needed = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
Point cur = new Point(sc.nextDouble(), Math.abs(sc.nextDouble()));
// always take the one with the lowest y coord
if (!needed.isEmpty() && needed.getLast().x == cur.x) {
if (cur.y >= needed.getLast().y) {
continue;
} else {
needed.removeLast();
}
}
// find "crosses"
while (needed.size() > 1) {
Point last = needed.getLast();
Point secondLast = needed.get(needed.size() - 2);
if (maxPoint(secondLast, last) > maxPoint(last, cur)) {
needed.removeLast();
} else {
break;
}
}
needed.addLast(cur);
}
// out of bounds
while (needed.size() > 1 && maxPoint(needed.getFirst(), needed.get(1)) < 0) {
needed.removeFirst();
}
while (needed.size() > 1) {
Point last = needed.getLast();
Point secondLast = needed.get(needed.size() - 2);
if (maxPoint(secondLast, last) > l) {
needed.removeLast();
} else {
break;
}
}
double ans = 0;
for (int x = 0; x < needed.size(); x++) {
// get critical points needed[x] is in charge of
Point left = new Point(0, 0);
Point right = new Point(l, 0);
if (x > 0) {
left.x = maxPoint(needed.get(x), needed.get(x - 1));
}
if (x < needed.size() - 1) {
right.x = maxPoint(needed.get(x), needed.get(x + 1));
}
if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) {
continue;
}
ans = Math.max(ans, Math.max(dist(needed.get(x), left), dist(needed.get(x), right)));
}
System.out.printf("%.6f\n", ans);
}
}