| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 544457 | rainboy | Mobile (BOI12_mobile) | C11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <math.h>
#include <stdio.h>
#define N 1000000
double min(double a, double b) { return a < b ? a : b; }
double max(double a, double b) { return a > b ? a : b; }
double hypot(double x, double y) { return sqrt(x * x + y * y); }
int xx[N], yy[N]; long long zz[N];
double f(int i, int j) {
return (double) (zz[i] - zz[j]) / (xx[i] - xx[j]) / 2;
}
int main() {
static int qu[N];
int n, x_, h, i, cnt;
double ans;
scanf("%d%d", &n, &x_);
cnt = 0;
for (i = 0; i < n; i++) {
scanf("%d%d", &xx[i], &yy[i]);
if (yy[i] < 0)
yy[i] = -yy[i];
zz[i] = (long long) xx[i] * xx[i] + (long long) yy[i] * yy[i];
if (cnt && xx[i] == xx[qu[cnt - 1]]) {
if (yy[qu[cnt - 1]] > yy[i])
cnt--;
else
continue;
}
while (cnt >= 2 && f(qu[cnt - 2], qu[cnt - 1]) > f(qu[cnt - 1], i))
cnt--;
qu[cnt++] = i;
}
ans = 0;
for (h = 0; h < cnt; h++) {
double l = h == 0 ? 0 : max(f(qu[h - 1], qu[h]), 0);
double r = h + 1 == cnt ? x_ : min(f(qu[h], qu[h + 1]), x_);
int x = xx[qu[h]], y = yy[qu[h]];
if (l <= r)
ans = max(ans, max(hypot(x - l, y), hypot(x - r, y)));
}
printf("%f\n", ans);
return 0;
}