Submission #1200871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200871		jalapen0p1ckle	먼 별 (KOI16_dist)	C++20	2 / 100	39 ms	3008 KiB

dist

//code by p1ckle/sft/yukicoder
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define int long long int
#define F first
#define X first
#define S second
#define Y second
#define mid ((start+end)/2)
#define all(x) x.begin(), x.end()
#define ub(a, b) upper_bound(all(a), b)
#define lb(a, b) lower_bound(all(a), b)
#define pb push_back
#define endl '\n'

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef long double ld;

const int inf = 1e18, mod = 1e9+7;
vpii dr4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, dr8 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

bool ccw(pii a, pii b, pii x) {

    return ((a.X*b.Y + b.X*x.Y + x.X*a.Y) - (a.Y*b.X + b.Y*x.X + x.Y*a.X) >= 0);

}

bool cw(pii a, pii b, pii x) {

    return ((a.X*b.Y + b.X*x.Y + x.X*a.Y) - (a.Y*b.X + b.Y*x.X + x.Y*a.X) <= 0);

}

int dis(pii a, pii b) {

    return (b.F-a.F)*(b.F-a.F)+(b.S-a.S)*(b.S-a.S);

}

int n, t, x[30003], y[30003], dx[30003], dy[30003], ans = inf;
vpii vp, uh, lh, hul;

int a, b;
signed main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> dx[i] >> dy[i];
    int l = 0, r = t;
    while (l < r) {

        int m[2] = {(l*2+r)/3, (l+r*2+2)/3}, tmp[2] = {0, 0};

        for (int k = 0; k < 2; k++) {

            vp.clear(); uh.clear(); lh.clear(); hul.clear();
            for (int i = 1; i <= n; i++) vp.pb({x[i]+m[k]*dx[i], y[i]+m[k]*dy[i]});
            sort(all(vp));

            uh.pb(vp[0]); uh.pb(vp[1]);
            for (int i = 2; i < n; i++) {

                if (uh.size() >= 2 && ccw(uh[uh.size()-2], uh[uh.size()-1], vp[i])) uh.pop_back();
                uh.pb(vp[i]);

            }
            lh.pb(vp[0]); lh.pb(vp[1]);
            for (int i = 2; i < n; i++) {

                if (lh.size() >= 2 && cw(lh[lh.size()-2], lh[lh.size()-1], vp[i])) lh.pop_back();
                lh.pb(vp[i]);

            }

            hul = uh;
            for (int i = lh.size()-2; i >= 0; i--) hul.pb(lh[i]);

            int nh = hul.size()-1;
            int p1 = 0, p2 = 1;
            for (; p1 < nh; p1++) {

                while (!ccw(hul[p1], hul[p1+1], {hul[p1].F+(hul[p2+1].F-hul[p2].F), hul[p1].S+(hul[p2+1].S-hul[p2].S)})) p2 = (p2+1)%nh;
                tmp[k] = max(tmp[k], dis(hul[p1], hul[p2]));

            }

        }

        ans = min({ans, tmp[0], tmp[1]});
        //cout << l << ' ' << r << ' ' << tmp[0] << ' ' << tmp[1] << endl;
        if (tmp[0] > tmp[1]) l = m[0]+1;
        else r = m[1]-1;

    }
    cout << l << endl << ans;

}

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