QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363809#8505. Almost Aligneducup-team2000#TL 1ms3952kbC++202.3kb2024-03-24 03:38:052024-03-24 03:38:05

Judging History

你现在查看的是最新测评结果

  • [2024-03-24 03:38:05]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3952kb
  • [2024-03-24 03:38:05]
  • 提交

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
...

output:


result: