QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363809 | #8505. Almost Aligned | ucup-team2000# | TL | 1ms | 3952kb | C++20 | 2.3kb | 2024-03-24 03:38:05 | 2024-03-24 03:38:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define f first
#define s second
#define lep(i,a,b) for (int i=(a); i <= (b); i++)
#define rep(i,b,a) for (int i = (b); i >= (a); i--)
typedef long double D;
const int inf = 1e16;
const D large_val = 1e100;
#define EPS 1e-12
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> x(n+1),y(n+1),vx(n+1),vy(n+1);
lep(i,1,n) {
cin >> x[i] >> y[i] >> vx[i] >> vy[i];
}
auto F = [&](D t) -> D {
D minx = large_val;
D maxx = -large_val;
D miny = large_val;
D maxy = -large_val;
lep(i,1,n) {
D xval = D(x[i]) + D(t) * D(vx[i]);
D yval = D(y[i]) + D(t) * D(vy[i]);
minx = min(minx, xval);
miny = min(miny, yval);
maxx = max(maxx, xval);
maxy = max(maxy, yval);
}
D ans = (maxy - miny) * (maxx - minx);
// cout << "t: " << t << ", ans: " << ans << "\n";
return ans;
};
lep(i,1,20) {
D l = 0;
D r = inf/i;
// cout << fixed << setprecision(10);
// while (r - l > EPS) {
// cout << "l: " << l << ", r: " << r << "\n";
lep(it,1,500) {
// cerr << "l: " << l << ", r: " << r << "\n";
D dif = r - l;
D m1 = l + dif * D(.4);
D m2 = l + dif * D(.6);
D ans1 = F(m1);
D ans2 = F(m2);
if (ans1 > ans2) l = m1;
else r = m2;
}
D ans1 = F(l);
l = inf/i;
r = inf;
// cerr << endl;
lep(it,1,500) {
// cerr << "l1: " << l << ", r1: " << r << "\n";
D dif = r - l;
D m1 = l + dif * D(.4);
D m2 = l + dif * D(.6);
D ans1 = F(m1);
D ans2 = F(m2);
if (ans1 > ans2) l = m1;
else r = m2;
}
D ans2 = F(l);
if (ans1 != ans2) {
cout << fixed << setprecision(15) << min(ans1, ans2) << "\n";
return 0;
} else if (i == 20) {
cout << fixed << setprecision(15) << ans1 << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3796kb
input:
4 0 0 10 10 0 0 10 10 10 10 -10 -10 10 0 -20 0
output:
22.222222222222222
result:
ok found '22.222222222', expected '22.222222222', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
3 0 -1 0 2 1 1 1 1 -1 1 -1 1
output:
0.000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
3 0 -1 0 -2 1 1 1 1 -1 1 -1 1
output:
4.000000000000000
result:
ok found '4.000000000', expected '4.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
1 0 0 0 0
output:
0.000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
4 1000000 1000000 -1 -1000000 1000000 -1000000 -1000000 1 -1000000 -1000000 1 1000000 -1000000 1000000 1000000 -1
output:
3999984000031.999953031539917
result:
ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'
Test #6:
score: -100
Time Limit Exceeded
input:
1000000 -871226 486657 -467526 31395 -65837 846554 469710 -907814 927993 -45099 713462 -276539 261942 483255 746021 811070 63449 -779486 588838 -413687 812070 -87868 -813499 -420768 112521 -622607 -832012 921368 -182120 517379 -401743 -837524 -685985 337832 643014 135144 12895 326935 -495720 930620 ...