Submission #714035

#	Time	Username	Problem	Language	Result	Execution time	Memory
714035		whqkrtk04	먼 별 (KOI16_dist)	C++17	81 / 100	393 ms	3304 KiB

dist

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
istream& operator>>(istream& is, vector<T>& v) { for(auto &i : v) is >> i; return is; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
    return g;
}
ll inv(ll a, ll m) {
    ll x, y; ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}

struct Point {
    ll x, y;
    Point(ll x, ll y) : x(x), y(y) {}
};
ostream& operator<<(ostream& out, Point a) {
    cout << '(' << a.x << ' ' << a.y << ')';
    return out;
}
int ccw(Point a, Point b, Point c) {
    ll x = (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
    return (int)(x > 0) - (int)(x < 0);
}
bool operator<(Point a, Point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
bool operator>(Point a, Point b) {
    return b < a;
}
bool operator<=(Point a, Point b) {
    return (a < b) || (a.x == b.x && a.y == b.y);
}
Point operator-(Point a, Point b) {
	return {a.x - b.x, a.y - b.y};
}
ll operator/(Point a, Point b){
	return a.x * b.y - a.y * b.x;
}
bool intersect(Point p1, Point p2, Point p3, Point p4) {
    int r1 = ccw(p1, p2, p3) * ccw(p1, p2, p4);
    int r2 = ccw(p3, p4, p1) * ccw(p3, p4, p2);
    if (r1 == 0 && r2 == 0) {
        if (p1 > p2) swap(p1, p2);
        if (p3 > p4) swap(p3, p4);
        return (!(p2 < p3 || p4 < p1) ? 1 : 0);
    } else {
        return (r1 <= 0 && r2 <= 0 ? 1 : 0);
    }
}

ll dst(Point p, Point q) {
    return (p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
}

vector<Point> convex_hull(vector<Point> A) {
    assert(A.size() >= 2);
    vector<Point> hull;
    swap(A[0], *min_element(A.begin(), A.end()));
    sort(A.begin()+1, A.end(), [&](Point a, Point b) {
        ll cw = ccw(A[0], a, b);
        if(cw) return cw > 0;
        return dst(A[0], a) < dst(A[0], b);
    });
    for(auto &i : A) {
        while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), i) <= 0) hull.pop_back();
        hull.push_back(i);
    }
    return hull;
}

ll rotating_calipers(vector<Point> A) {
	// A[0] should be mininum element, A should be a convex polygon and sorted in ccw
	int n = A.size(); A.push_back(A[0]);
	int l = 0, r = max_element(A.begin(), A.end()) - A.begin();
    ll ret = 0LL;
	while (1) {
	// A[l], A[r] are antipodal points
        // your code here
        ret = max(ret, dst(A[l], A[r]));
		if (n == 2 || r == n) break;
		if ((A[l + 1] - A[l]) / (A[r + 1] - A[r]) <= 0) {
			l += 1;
		}
		else r += 1;
	}
    return ret;
}

ll solve(int n, int t, vector<pii>& IXY, vector<pii>& DXY) {
    vector<Point> XY;
    for(int i = 0; i < n; i++) {
        Point p = {0, 0};
        p.x = IXY[i].fi+(ll)t*DXY[i].fi;
        p.y = IXY[i].se+(ll)t*DXY[i].se;
        XY.push_back(p);
    }
    vector<Point> hull = convex_hull(XY);
    return rotating_calipers(hull);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t; cin >> n >> t;
    vector<pii> IXY(n), DXY(n);
    for(int i = 0; i < n; i++)
        cin >> IXY[i].fi >> IXY[i].se >> DXY[i].fi >> DXY[i].se;
    int l = 0, r = t;
    while(r-l >= 3) {
        int s = (l*2+r)/3, e = (l+r*2)/3;
        ll ss = solve(n, s, IXY, DXY);
        ll ee = solve(n, e, IXY, DXY);
        if(ss <= ee) r = e;
        else l = s;
    }
    int res = -1;
    ll ans = LLINF;
    for(int i = l; i <= r; i++) {
        ll tmp = solve(n, i, IXY, DXY);
        if(tmp < ans) ans = tmp, res = i;
    }
    assert(res != -1);
    cout << res << "\n" << ans << "\n";
    return 0;
}

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