QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#361988#8505. Almost Aligneducup-team2303#TL 2ms10080kbC++202.6kb2024-03-23 13:50:292024-03-23 13:50:30

Judging History

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

  • [2024-03-23 13:50:30]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:10080kb
  • [2024-03-23 13:50:29]
  • 提交

answer

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <int, int> 
using namespace std;
inline int read(void) {
    int x=0,sgn=1; char ch=getchar();
    while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
    while(47<ch&&ch<58) {x=x*10+ch-48;   ch=getchar();}
    return sgn? x:-x;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*
    write((Ans%p+p)%p); pls
*/
#define double long double
int n;
double mid,Ans;
int x[1000006],y[1000006],vx[1000006],vy[1000006];
inline void chkmin(double&x,double y) { x=min(x,y); }
inline void chkmax(double&x,double y) { x=max(x,y); }
inline double check(double t) {
    double mix,mxx,miy,mxy;
    mix=mxx=x[1]+vx[1]*t;
    miy=mxy=y[1]+vy[1]*t;
    for(int i=2; i<=n; ++i) {
        chkmin(mix,x[i]+vx[i]*t);
        chkmax(mxx,x[i]+vx[i]*t);
        chkmin(miy,y[i]+vy[i]*t);
        chkmax(mxy,y[i]+vy[i]*t);
    }
    // cerr<<"t = "<<t<<'|'<<mix<<' '<<mxx<<' '<<miy<<' '<<mxy<<endl;
    chkmin(Ans,(mxx-mix)*(mxy-miy));
    return (mxx-mix)*(mxy-miy);
}
inline double checkX(double t) {
    double mix,mxx;
    mix=mxx=x[1]+vx[1]*t;
    for(int i=2; i<=n; ++i) {
        chkmin(mix,x[i]+vx[i]*t);
        chkmax(mxx,x[i]+vx[i]*t);
    }
    return mxx-mix;
}
inline double checkY(double t) {
    double miy,mxy;
    miy=mxy=y[1]+vy[1]*t;
    for(int i=2; i<=n; ++i) {
        chkmin(miy,y[i]+vy[i]*t);
        chkmax(mxy,y[i]+vy[i]*t);
    }
    return (mxy-miy);
}
inline double checkmid(double t) {
    return abs(log(checkX(t))-log(checkY(t)));
}
inline void qmid(void) {
    double L=0,R=1000000000000;
    for(int t=0; t<=400; ++t) {
        double ml=(2*L+R)/3;
        double mr=(L+2*R)/3;
        if(check(ml)<check(mr)) R=mr;
        else L=ml;
    }
    mid=L;
}
inline void solve(double L,double R) {
    for(int t=0; t<=400; ++t) {
        double ml=(2*L+R)/3;
        double mr=(L+2*R)/3;
        if(check(ml)<check(mr)) R=mr;
        else L=ml;
    }
    check(L);
}
signed main() {
    // freopen("localinput","r",stdin);
    // freopen("localoutput","w",stdout);
    n=read(); Ans=1e27;
    for(int i=1; i<=n; ++i) x[i]=read(),y[i]=read(),vx[i]=read(),vy[i]=read();
    qmid();
    // cerr<<mid<<endl;
    solve(0,mid);
    solve(mid,1000000000.0);
    printf("%.12Lf\n",Ans);
    // fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10004kb

input:

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

output:

22.222222222222

result:

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

Test #2:

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

input:

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

output:

0.000000000000

result:

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

Test #3:

score: 0
Accepted
time: 2ms
memory: 10076kb

input:

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

output:

4.000000000000

result:

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

Test #4:

score: 0
Accepted
time: 1ms
memory: 9968kb

input:

1
0 0 0 0

output:

0.000000000000

result:

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

Test #5:

score: 0
Accepted
time: 1ms
memory: 9976kb

input:

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

output:

3999984000031.999952077866

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: