oj.uz

Submission #681401

# Submission time Handle Problem Language Result Execution time Memory
681401 2023-01-13T03:08:19 Z Kamisama None (KOI16_dist) C++14
100 / 100
 224 ms 3816 KB 
#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 - 1;
    while(l <= r) {
        int m = (l + r) / 2;
        if(solve(m) > solve(m + 1)) l = m + 1;
        else r = m - 1;
    }

    cout << l << '\n' << solve(l);

    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3264 KB Output is correct
9 Correct 2 ms 3144 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3264 KB Output is correct
9 Correct 2 ms 3144 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 6 ms 3152 KB Output is correct
12 Correct 7 ms 3156 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 6 ms 3156 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct
16 Correct 9 ms 3148 KB Output is correct
17 Correct 6 ms 3152 KB Output is correct
18 Correct 4 ms 3156 KB Output is correct
19 Correct 5 ms 3160 KB Output is correct
20 Correct 7 ms 3156 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3812 KB Output is correct
2 Correct 55 ms 3664 KB Output is correct
3 Correct 54 ms 3632 KB Output is correct
4 Correct 46 ms 3780 KB Output is correct
5 Correct 60 ms 3796 KB Output is correct
6 Correct 62 ms 3632 KB Output is correct
7 Correct 36 ms 3568 KB Output is correct
8 Correct 31 ms 3484 KB Output is correct
9 Correct 56 ms 3808 KB Output is correct
10 Correct 55 ms 3632 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3264 KB Output is correct
9 Correct 2 ms 3144 KB Output is correct
10 Correct 2 ms 3028 KB Output is correct
11 Correct 6 ms 3152 KB Output is correct
12 Correct 7 ms 3156 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 6 ms 3156 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct
16 Correct 9 ms 3148 KB Output is correct
17 Correct 6 ms 3152 KB Output is correct
18 Correct 4 ms 3156 KB Output is correct
19 Correct 5 ms 3160 KB Output is correct
20 Correct 7 ms 3156 KB Output is correct
21 Correct 70 ms 3812 KB Output is correct
22 Correct 55 ms 3664 KB Output is correct
23 Correct 54 ms 3632 KB Output is correct
24 Correct 46 ms 3780 KB Output is correct
25 Correct 60 ms 3796 KB Output is correct
26 Correct 62 ms 3632 KB Output is correct
27 Correct 36 ms 3568 KB Output is correct
28 Correct 31 ms 3484 KB Output is correct
29 Correct 56 ms 3808 KB Output is correct
30 Correct 55 ms 3632 KB Output is correct
31 Correct 200 ms 3808 KB Output is correct
32 Correct 215 ms 3540 KB Output is correct
33 Correct 217 ms 3660 KB Output is correct
34 Correct 224 ms 3764 KB Output is correct
35 Correct 210 ms 3796 KB Output is correct
36 Correct 173 ms 3668 KB Output is correct
37 Correct 170 ms 3808 KB Output is correct
38 Correct 133 ms 3796 KB Output is correct
39 Correct 152 ms 3816 KB Output is correct
40 Correct 204 ms 3764 KB Output is correct
41 Correct 216 ms 3772 KB Output is correct
42 Correct 209 ms 3792 KB Output is correct