This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |