먼 별 (백준 13310)

안녕하세요. 오늘은 별의 거리를 잴거예요.

문제

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

아이디어

이거 + 이거입니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define ll long long
#define pii pair <ll,ll>
using namespace std;

ll CCW(pii A, pii B, pii C)
{
    ll ax = A.first, ay = A.second, bx = B.first, by = B.second, cx = C.first, cy = C.second;
    ll ccw = ax * (by - cy) + bx * (cy - ay) + cx * (ay - by);
    if (ccw < 0) return -1;
    if (ccw > 0) return 1;
    return 0;
}
ll dis(pii A, pii B)
{
    return (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
}

bool ycmp(pii A, pii B)
{
    if (A.second != B.second) return A.second < B.second;
    return A < B;
}
pii low_dot;
bool cmp(pii A, pii B)
{
    if (CCW(low_dot, A, B) > 0) return true;
    if (CCW(low_dot, A, B) == 0) return dis(low_dot, A) < dis(low_dot, B);
    return false;
}

ll N;
vector <pii> dot;
vector <ll> dx, dy;
vector <pii> change(ll time) //time시간이 지난 후 점들의 모습
{
    vector <pii> ans;
    for (int i = 0; i < N; i++)
        ans.push_back({ dot[i].first + dx[i] * time,dot[i].second + dy[i] * time });
    return ans;
}
vector <pii> make_convex(vector <pii> v)
{
    ll new_N = v.size();
    sort(v.begin(), v.end(), ycmp);
    low_dot = v[0];
    sort(v.begin() + 1, v.end(), cmp);

    ll stk[30303] = { 0 }, top = 2;
    stk[0] = 0; stk[1] = 1;
    for (int i = 2; i < new_N; i++)
    {
        while (top >= 2 && CCW(v[i], v[stk[top - 2]], v[stk[top - 1]]) <= 0)
            top--;
        stk[top++] = i;
    }

    vector <pii> ans;
    for (int i = 0; i < top; i++)
        ans.push_back(v[stk[i]]);
    return ans;
}
ll RoCal(vector <pii> v)
{
    ll new_N = v.size(), i, next_i, j = 0, next_j;
    ll ans = 0;
    for (i = 0; i < new_N; i++)
    {
        next_i = (i + 1) % N;
        while (true)
        {
            ans = max(ans, dis(v[i], v[j]));
            next_j = (j + 1) % N;

            pii v1, v2;
            v1.first = v[i].first - v[next_i].first;
            v1.second = v[i].second - v[next_i].second;
            v2.first = v[j].first - v[next_j].first;
            v2.second = v[j].second - v[next_j].second;

            if (CCW({ 0,0 }, v1, v2) > 0)
                j = next_j;
            else break;
        }
        ans = max(ans, dis(v[i], v[j]));
    }

    return ans;
}
ll f(ll time)
{
    ll ans = RoCal(make_convex(change(time)));
    return ans;
}
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll M, i, a, b, c, d;
    cin >> N >> M;
    for (i = 0; i < N; i++)
    {
        cin >> a >> b >> c >> d;
        dot.push_back({ a,b });
        dx.push_back(c);
        dy.push_back(d);
    }

    ll left = 0, right = M;
    while (right - left >= 3)
    {
        ll llr = (left * 2 + right) / 3, lrr = (left + right * 2) / 3;
        if (f(llr) <= f(lrr)) right = lrr;
        else left = llr;
    }

    ll ans = 1e18, p = 0;
    for (i = left; i <= right; i++)
    {
        ll x = f(i);
        if (x < ans)
        {
            ans = x;
            p = i;
        }
    }
    cout << p << "\n" << ans;
}

감사합니다.