Submission #151222

#TimeUsernameProblemLanguageResultExecution timeMemory
151222ChoKang먼 별 (KOI16_dist)C++14
100 / 100
661 ms4492 KiB
#include <bits/stdc++.h> #define MAX_N 30100 #define eb emplace_back #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; struct point{ ll x, y, dx, dy; point(ll x = 0, ll y = 0, ll dx = 0, ll dy = 0): x(x), y(y), dx(dx), dy(dy) {} }; int n, t; vector<point> p, e, hull; int ccw(point a, point b, point c){ ll val = (b.x-a.x) * (c.y-a.y) - (b.y-a.y) * (c.x-a.x); if(val > 0) return 1; if(val < 0) return -1; return val; } bool comp(point p1, point p2){ int val = ccw(e[0], p1, p2); if(val > 0) return true; if(val < 0) return false; if(p1.x != p2.x) return p1.x < p2.x; return p1.y < p2.y; } void graham_scan(){ int Size = 0; for(int i = 0; i < n; i++){ while(Size >= 2 && ccw(hull[Size-2], hull[Size-1], e[i]) <= 0){ Size--; hull.pop_back(); } hull.eb(e[i]); Size++; } } ll rotating(int T){ int pivot = 0; for(int i = 0; i < n; i++){ e.eb(p[i].x + T*p[i].dx, p[i].y + T*p[i].dy, 0, 0); if(e[pivot].x > e[i].x || (e[pivot].x == e[i].x && e[pivot].y > e[i].y)) pivot = i; } swap(e[0], e[pivot]); sort(e.begin()+1, e.end(), comp); graham_scan(); int Size = hull.size(), ni, nj, j = 1; point a, b, c; ll ret = 0; for(int i = 0; i < Size; i++){ ni = (i+1)%Size; while(1){ nj = (j+1)%Size; a = { 0, 0, 0, 0 }; b={ hull[ni].x-hull[i].x, hull[ni].y-hull[i].y, 0, 0 }; c={ hull[nj].x-hull[j].x, hull[nj].y-hull[j].y, 0, 0 }; int k = ccw(a, b, c); if(k > 0) j = nj; else break; } ll val = (hull[i].x - hull[j].x) * (hull[i].x - hull[j].x) + (hull[i].y - hull[j].y) * (hull[i].y - hull[j].y); ret = max(ret, val); } e.clear(); hull.clear(); return ret; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> t; for(ll i = 0, x1, y1, dx1, dy1; i < n; i++){ cin >> x1 >> y1 >> dx1 >> dy1; p.eb(x1, y1, dx1, dy1); } int S = 0, E = t; ll ans = LLONG_MAX, ind = 0; while(S < E){ int f1 = S +(E-S)/3, f2 = E -(E-S)/3; ll val1 = rotating(f1), val2 = rotating(f2); if(val1 > val2) S = f1+1; else E = f2-1; } cout << S << endl << rotating(S) <<endl; return 0; }

Compilation message (stderr)

dist.cpp: In function 'int main()':
dist.cpp:85:5: warning: unused variable 'ans' [-Wunused-variable]
  ll ans = LLONG_MAX, ind = 0;
     ^~~
dist.cpp:85:22: warning: unused variable 'ind' [-Wunused-variable]
  ll ans = LLONG_MAX, ind = 0;
                      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...