QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#361988 | #8505. Almost Aligned | ucup-team2303# | TL | 2ms | 10080kb | C++20 | 2.6kb | 2024-03-23 13:50:29 | 2024-03-23 13:50:30 |
Judging History
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 ...