QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382203#8505. Almost Alignedkevinshan#TL 0ms3952kbC++172.6kb2024-04-08 06:02:212024-04-08 06:02:21

Judging History

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

  • [2024-04-08 06:02:21]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3952kb
  • [2024-04-08 06:02:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long double
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n; cin>>n;
    ll x[n], y[n], vx[n], vy[n];
    for(int i=0; i<n; i++) cin>>x[i]>>y[i]>>vx[i]>>vy[i];

    ll ar = 5e18;
    vector<ll> deltas = {1e-7, 1e-8, 1e-9, 1e-10, 1e-11, 1e-12, 1e-13, 1e-14};
    for(auto delta:deltas){
        ll l = 0;
        ll r = 2e12;
        while(r - l >= delta) {
            ll m = (l+r)/2.0;
            ll mnx = x[0] + vx[0] * m;
            ll mxx = x[0] + vx[0] * m;
            ll mny = y[0] + vy[0] * m;
            ll mxy = y[0] + vy[0] * m;
            for(int i=1; i<n; i++){
                mnx = min(mnx, x[i] + vx[i] * m);
                mxx = max(mxx, x[i] + vx[i] * m);
                mny = min(mny, y[i] + vy[i] * m);
                mxy = max(mxy, y[i] + vy[i] * m);
            }

            ll md = m + delta;

            ll mnxd = x[0] + vx[0] * md;
            ll mxxd = x[0] + vx[0] * md;
            ll mnyd = y[0] + vy[0] * md;
            ll mxyd = y[0] + vy[0] * md;
            for(int i=1; i<n; i++){
                mnxd = min(mnxd, x[i] + vx[i] * md);
                mxxd = max(mxxd, x[i] + vx[i] * md);
                mnyd = min(mnyd, y[i] + vy[i] * md);
                mxyd = max(mxyd, y[i] + vy[i] * md);
            }

            if((mxx - mnx) * (mxy - mny) > (mxxd - mnxd) * (mxyd - mnyd) + delta){
                l = m;
            }
            else {
                r = m;
            }
            // cout<<l<<"|"<<r<<"\n";
            // cout<<(mxx - mnx) * (mxy - mny)<<"\n";
            ar = min(ar, (mxx - mnx) * (mxy - mny));
            ar = min(ar, (mxxd - mnxd) * (mxyd - mnyd));
        }
        for(int i=-10; i<=10; i++){
            ll m = i * delta/10 + l;
            if(m<0) continue;
            ll mnx = x[0] + vx[0] * m;
            ll mxx = x[0] + vx[0] * m;
            ll mny = y[0] + vy[0] * m;
            ll mxy = y[0] + vy[0] * m;
            for(int i=1; i<n; i++){
                mnx = min(mnx, x[i] + vx[i] * m);
                mxx = max(mxx, x[i] + vx[i] * m);
                mny = min(mny, y[i] + vy[i] * m);
                mxy = max(mxy, y[i] + vy[i] * m);
            }
            ar = min(ar, (mxx - mnx) * (mxy - mny));
        }
    }
    cout<<fixed<<setprecision(25)<<ar;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3928kb

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

22.2222222222222351075554547

result:

ok found '22.222222222', expected '22.222222222', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3
0 -1 0 2
1 1 1 1
-1 1 -1 1

output:

0.0000000000000005607493636

result:

ok found '0.000000000', expected '0.000000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

3
0 -1 0 -2
1 1 1 1
-1 1 -1 1

output:

4.0000000000000000000000000

result:

ok found '4.000000000', expected '4.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

1
0 0 0 0

output:

0.0000000000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

4
1000000 1000000 -1 -1000000
1000000 -1000000 -1000000 1
-1000000 -1000000 1 1000000
-1000000 1000000 1000000 -1

output:

3999984000031.9999520778656005859375000

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: