Submission #680774

#	Time	Username	Problem	Language	Result	Execution time	Memory
680774		Kamisama	먼 별 (KOI16_dist)	C++14	100 / 100	363 ms	3156 KiB

dist

#include <iostream>
#include <cstdlib>
#include <climits>
#include <algorithm>
using namespace std;
const int MAXN = 3e4 + 7;

struct Star {
    long long x, y, dx, dy;
    Star(long long x=0, long long y=0, long long dx=0, long long dy=0)
        : x(x), y(y), dx(dx), dy(dy) {}

    Star operator-(const Star &other) const {
        return Star(x - other.x, y - other.y);
    }

    long long operator%(const Star &other) const {
        return x * other.y - y * other.x;
    }
};

int n, t, hull_size;
Star a[MAXN], p[MAXN];
Star convex_hull[MAXN];

int ccw(const Star &A, const Star &B, const Star &C) {
    long long res = A % B + B % C + C % A;
    return (res > 0) - (res < 0);
}

long long get_distance(const Star &A, const Star &B) {
    long long dx = A.x - B.x;
    long long dy = A.y - B.y;
    return dx * dx + dy * dy;
}

long long solve(int k) {
    for(int i = 1; i <= n; i++) {
        p[i] = Star(a[i].x + k * a[i].dx, a[i].y + k * a[i].dy);
    }

    swap(p[1], *min_element(p + 1, p + n + 1, [](const Star &A, const Star &B) {
        return A.x < B.x || (A.x == B.x && A.y < B.y);
    }));
    sort(p + 2, p + n + 1, [](const Star &A, const Star &B) {
        int not_linear = ccw(p[1], A, B);
        if(not_linear) return not_linear > 0;
        return get_distance(p[1], A) < get_distance(p[1], B);
    });

    hull_size = 0;
    for(int i = 1; i <= n; i++) {
        while(hull_size >= 2 && ccw(convex_hull[hull_size - 1], convex_hull[hull_size], p[i]) <= 0){
            hull_size--;
        }
        convex_hull[++hull_size] = p[i];
    }

    long long res = 0;
    for(int i = 1, j = 1; i <= hull_size; i++) {
        while(j < hull_size && ccw(Star(0, 0), convex_hull[i + 1] - convex_hull[i], convex_hull[j + 1] - convex_hull[j]) >= 0) {
            res = max(res, get_distance(convex_hull[i], convex_hull[j]));
            j++;
        }
        res = max(res, get_distance(convex_hull[i], convex_hull[j]));
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> t;
    for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].dx >> a[i].dy;

    int l = 0, r = t;
    while(r - l >= 3) {
        int m1 = (2 * l + r) / 3;
        int m2 = (l + 2 *  r) / 3;
        if(solve(m1) > solve(m2)) l = m1;
        else r = m2;
    }

    int date = 0;
    long long res = LLONG_MAX;
    for(int k = l; k <= r; k++) {
        long long potential = solve(k);
        if(res > potential) {
            res = potential;
            date = k;
        }
    }

    cout << date << '\n' <<  res;

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 40 / 40
• Subtask 3: 39 / 39
• Subtask 4: 19 / 19