3346번: Mobile

https://www.acmicpc.net/problem/3346

$O(n)$

점들 중 x좌표가 같다면 y=0에 더 먼 점을 제외시킨다.
각 연속한 두 점을 지나고 y=0에 중심이 있는 원 중심의 x좌표가 증가하는 점들의 나열을 구하면 문제를 해결할 수 있다.
이러한 점들의 나열은 사전에 점들이 x좌표를 기준으로 정렬되어 있을 경우 monotonous stack을 이용해 O(n)에 구할 수 있다.

u-v를 점 u,v를 지나고 중심이 y=0에 있는 원,
f(u,v)를 이러한 원 중심의 x좌표라고 정의하자.
x좌표가 증가하는 순으로 세 점 a,b,c가 주어졌을 때
a-c 밖에 b가 있다 <-> f(a,c)>f(b,c)
이다.
이를 이용해 점들을 저장하는 스택을 준비해서
top이 원 (top-1)-(새로운 점) 밖에 있는 한 pop을 해주고 새로운 점을 추가하는 방식으로 처음 제시한 조건의 나열을 구할 수 있다.

문제의 조건에 따라 원의 중심은 선분 y=0 & 0<=x<=l에 있어야 한다.
(0,0)과 (l,0)에 가장 가까운 점 s,e를 구해서
중심 (0,0)과 s를 지나는 원, 중심 (l,0)과 e를 지나는 원, s~e 사이의 점들을 가지고 위 방법으로 구한 원들 중 최대 반지름이 답이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e6;
struct point {
    double x, y;
}p[MXN], stk[MXN];
int n, l, top, s, e;
double r;
double crs(point i, point j) { return ((i.y*i.y - j.y*j.y) / (i.x - j.x) + i.x + j.x) / 2; }
int main() {
    scanf("%d%d", &n, &l);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        p[i].y = abs(p[i].y);
        if (hypot(p[s].x, p[s].y)>hypot(p[i].x, p[i].y)) s = i;
        if (hypot(p[e].x - l, p[e].y) > hypot(p[i].x - l, p[i].y)) e = i;
    }
    r = max(hypot(p[s].x, p[s].y), hypot(p[e].x - l, p[e].y));
    stk[top] = p[s];
    for (int i = s + 1; i <= e; i++) if (stk[top].x<p[i].x || stk[top].y>p[i].y) {
        while (stk[top].x == p[i].x || top&&crs(stk[top - 1], p[i]) > crs(stk[top], p[i])) top--;
        stk[++top] = p[i];
    }
    for (int i = 0; i < top; i++) {
        point t = { crs(stk[i],stk[i + 1]),0 };
        r = max(r, hypot(t.x - stk[i].x, stk[i].y));
    }
    printf("%lf", r);
    return 0;
}