Boj 13310) 먼 별

문제

백준 13310

설명

특정 시점에서의 별들 간의 최대거리를 구하는 함수를 만들어 함수 값이 최소가 되는 시점을 구하는 Paramatric Search 문제이다. 별들 간의 최대거리는 회전하는 캘리버스 알고리즘을 알고있다면 간단히 구현할 수 있다. 문제는 T 의 범위가 커서 브루트포스로는 답을 구할 수 없다는 것이다. 이를 삼분탐색을 사용해 시간을 로그단위로 만드는 것이 핵심이다.

하지만 위의 전략은 Unimodal 한 함수에서만 가능한데 어떻게 이를 확신할 수 있을까?

이는 의외로 간단한데, \(\mathrm{N}\choose{2}\) 에 달하는 별들의 쌍 각각에 대한 시간에 따른 거리의 함수는 Unimodal 한 함수이다. 정확히는 V 모양을 가진 함수가 되겠다. V 모양 함수가 합쳐진다면 최솟값이 많아야 2개 이상일 것이다. 여기서 우리가 구하는 것이 거리의 최댓값인 것을 생각하면, 적어도 둘 중 한 함수의 최솟값에선 다른 함수의 값이 더 크므로 최소값은 하나가 된다는 것을 알 수 있다. 그래서 W 모양은 존재할 수 없다. 이러한 과정을 반복하여 우리가 사용할 함수를 만들 수 있으므로, 그 결과 역시 Unimodal 한 함수가 되는 것이다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{T}}\))

코드

using ll = long long;
template<typename ll = long long>
struct VEC {
    ll x, y;
    VEC    operator+(const VEC& in) const { return { x + in.x, y + in.y }; }
    VEC    operator-(const VEC& in) const { return { x - in.x, y - in.y }; }
    bool operator  <(const VEC& in) const { return x == in.x ? y < in.y : x < in.x; }
    bool operator <=(const VEC& in) const { return x == in.x ? y <= in.y : x <= in.x; }
    bool operator ==(const VEC& in) const { return x == in.x && y == in.y; }
    ll Cross(const VEC& in) const { return  x * in.y - y * in.x; }
    ll Dist2(const VEC& in) const {
        return (x - in.x) * (x - in.x) + (y - in.y) * (y - in.y);
    }
    friend ll CCW(const VEC& a, VEC b, VEC c)
    {
        b = b - a;
        c = c - a;
        return  b.x * c.y - b.y * c.x;
    }
};

using ll = long long;
using ii = VEC<ll>;
ii arr[30001];

struct START {
    ll x, y, dx, dy;
} inputs[30001];

ll Calc(int n, ll day)
{
    for (int i = 0; i < n; i++)
        arr[i] = { inputs[i].x + (ll)inputs[i].dx * day, inputs[i].y + (ll)inputs[i].dy * day };

    n -= arr + n - unique(arr, arr + n);
    swap(arr[0], arr[min_element(arr, arr + n) - arr]);
    sort(arr + 1, arr + n, [base = arr[0]](ii& a, ii& b) {
        ll c = CCW(base, a, b);
        return c != 0 ? c > 0 : base.Dist2(a) < base.Dist2(b);
    });

    deque<int> st; st.push_back(0); st.push_back(1);
    for (int i = 2; i < n; i++)
    {
        while (st.size() > 1 && 0 >= CCW(arr[st[st.size() - 2]], arr[st[st.size() - 1]], arr[i]))
            st.pop_back();
        st.push_back(i);
    }

    int s = st.size();
    ll ans = max(ans, arr[st[0]].Dist2(arr[st[1]]));
    for (int l = 0, r = 1; r != 0; )
    {
        ll theta = (arr[st[(l + 1) % s]] - arr[st[l]]).Cross(arr[st[r]] - arr[st[(r + 1) % s]]);
        theta > 0 ? l = (l + 1) % s : r = (r + 1) % s;
        ans = max(ans, arr[st[l]].Dist2(arr[st[r]]));
    }

    return ans;
}

int main()
{
    fastio;
    int N, T;
    cin >> N >> T;
    for (int i = 0; i < N; i++)
        cin >> inputs[i].x >> inputs[i].y >> inputs[i].dx >> inputs[i].dy;

    int s = 0, e = T;
    while (e - s > 2)
    {
        int d = (e - s) / 3;
        int p = s + d, q = s + (d << 1);
        ll pv = Calc(N, p), qv = Calc(N, q);
        pv > qv ? s = p + 1 : e = q - 1;
    }

    ll ans = 1e18, ans_i = -1;
    for (int i = s; i <= e; i++)
    {
        ll d = Calc(N, i);
        if (d < ans)
        {
            ans = d;
            ans_i = i;
        }
    }
    cout << ans_i << '\n' << ans;
}