Submission #544642

#	Time	Username	Problem	Language	Result	Execution time	Memory
544642		pokmui9909	먼 별 (KOI16_dist)	C++17	100 / 100	581 ms	4320 KiB

dist

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
 
#define x first
#define y second
using Point = pair<ll, ll>;
Point operator+ (Point p, Point q) {return Point(p.x + q.x, p.y + q.y);}
Point operator- (Point p, Point q) {return Point(p.x - q.x, p.y - q.y);}
ll    operator* (Point p, Point q) {return p.x * q.x + p.y * q.y;}
ll    operator/ (Point p, Point q) {return p.x * q.y - q.x * p.y;}
ll CCW(Point p, Point q, Point r) {return (q - p) / (r - q);}
ll Dist(Point p, Point q) {return pow(p.x - q.x, 2) + pow(p.y - q.y, 2);}
 
vector<Point> convex_hull(vector<Point> P){
    ll N = P.size();
    sort(P.begin(), P.end());
    sort(P.begin() + 1, P.end(), [&](Point a, Point b) -> bool {
        if(CCW(P[0], a, b) != CCW(P[0], b, a)) return CCW(P[0], a, b) < CCW(P[0], b, a);
        else if(a.x != b.x) return a.x < b.x;
        else return a.y < b.y;
    });
    vector<Point> H;
    for(int i = 0; i < N; i++){
        while(H.size() >= 2 && CCW(H[H.size() - 2], H[H.size() - 1], P[i]) >= 0) H.pop_back();
        H.push_back(P[i]);
    }
    return H;
}
ll rotating_callipers(vector<Point> P){
    P = convex_hull(P);
    ll N = P.size();
    ll L = 0, R = 0;
    for(int i = 1; i < N; i++){
        if(P[i].x < P[L].x) L = i;
        if(P[i].x > P[R].x) R = i;
    }
    ll ans = Dist(P[L], P[R]);
    for(int i = 0; i < N; i++){
        if((P[(L + 1) % N] - P[L]) / (P[(R + 1) % N] - P[R]) > 0){
            L = (L + 1) % N;
        } else {
            R = (R + 1) % N;
        }
        ans = max(ans, Dist(P[L], P[R]));
    }
    return ans;
}
ll N, T;
pair<Point, Point> A[30005];
ll f(ll t){
    vector<Point> P(N);
    for(int i = 0; i < N; i++){
        P[i].x = A[i].x.x + A[i].y.x * t;
        P[i].y = A[i].x.y + A[i].y.y * t;
    }
    return rotating_callipers(P);
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
 
    cin >> N >> T;
    for(int i = 0; i < N; i++){
        cin >> A[i].x.x >> A[i].x.y >> A[i].y.x >> A[i].y.y;
    }
    ll L = 0, R = T;
    while(R - L > 3){
        ll p = (L * 2 + R) / 3, q = (L + R * 2) / 3;
        if(f(p) <= f(q)) R = q;
        else L = p;
    }
    ll mn = 1e18, idx = 0;
    for(int i = L; i <= R; i++){
        ll v = f(i);
        if(mn > v){
            mn = v;
            idx = i;
        }
    }
    cout << idx << '\n' << mn;
}

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