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;
typedef unsigned long long ull;
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-b.y) - (b.y-a.y) * (c.x-b.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]);
}
}
ull 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;
ull 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;
}
ull val = (ull)((hull[i].x - hull[j].x) * (hull[i].x - hull[j].x))
+ (ull)((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;
ull ans = ULLONG_MAX, ind = 0;
while(S < E-3){
int f1 = (2*S + E)/3, f2 = (S + 2*E)/3;
ull val1 = rotating(f1), val2 = rotating(f2);
if(val1 > val2) S = f1 + 1;
else if(val1 < val2) E = f2 - 1;
else E = f2 -1;
}
for(int i = S; i <= E; i++){
ull val = rotating(i);
if(val < ans){ ind = i; ans = val; }
}
cout << ind << endl << ans <<endl;
return 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... |