QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515208 | #2268. Solar Car | ucup-team052 | WA | 1ms | 6480kb | C++23 | 2.5kb | 2024-08-11 16:02:32 | 2024-08-11 16:02:32 |
Judging History
answer
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define N 2005
#define ll long long
struct Vec
{
int x,y;
Vec(int a=0,int b=0) {x=a,y=b;}
double norm() {return sqrt(1LL*x*x+1LL*y*y);}
};
const double inf=1e100;
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
ll cross(const Vec &x,const Vec &y) {return 1LL*x.x*y.y-1LL*x.y*y.x;}
int sgn(ll x)
{
if(x<0) return -1;
else if(x>0) return 1;
else return 0;
}
int ccw(const Vec &x,const Vec &y,const Vec &z) {return sgn(cross(y-x,z-x));}
Vec a[N];
Vec o(0,0);
int id[N];
int n,ok[N][N];
double dis[N][N],ans[N][N];
void solve(int l,int r)
{
for(int i=l;i<=r;i++)
{
Vec premn=a[id[i%n]],u=a[id[i%n]];
int lst=id[i%n];
for(int j=i-1;j>=l;j--)
{
Vec v=a[id[j%n]];
if(ccw(u,premn,v)==-1)
{
dis[id[i%n]][id[j%n]]=dis[id[i%n]][lst]+dis[lst][id[j%n]];
dis[id[j%n]][id[i%n]]=dis[id[i%n]][id[j%n]];
}
else
{
dis[id[i%n]][id[j%n]]=(u-v).norm();
dis[id[j%n]][id[i%n]]=dis[id[i%n]][id[j%n]];
premn=v,lst=id[j%n];
}
}
}
}
signed main() {
#ifdef xay5421
freopen("b.in","r",stdin);
#endif
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
for(int i=0;i<n;i++) id[i]=i;
sort(id,id+n,[&](int x,int y){
return atan2(a[x].x,a[x].y)<atan2(a[y].x,a[y].y);
});
int pos0=0,pos1=0,pos2=0,pos3=0;
for(int i=0;i<n;i++)
{
double val=atan2(a[id[i]].x,a[id[i]].y);
if(val<=atan2(1,0)) pos3=i+1;
if(val<=atan2(0,1)) pos2=i+1;
if(val<=atan2(-1,0)) pos1=i+1;
}
// for(int i=0;i<n;i++) printf("%d %d\n",a[id[i]].x,a[id[i]].y);
// printf("%d %d %d %d\n",pos0,pos1,pos2,pos3);
solve(pos0,pos2-1);
solve(pos1,pos3-1);
solve(pos2,pos0+n-1);
solve(pos3,pos1+n-1);
// for(int i=0;i<n;i++) for(int j=0;j<n;j++) printf("%2.2lf%c",dis[i][j]," \n"[j==n-1]);
for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(dis[i][j]==0) dis[i][j]=(a[i]-a[j]).norm();
cerr<<clock()<<endl;
for(int i=0;i<n;i++) for(int j=i;j<n;j++)
{
for(int k=0;k<n;k++) ans[i+1][j+1]=max(ans[i+1][j+1],dis[i][k]+dis[j][k]);
ans[j+1][i+1]=ans[i+1][j+1];
}
cerr<<clock()<<endl;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j]=ans[i][j]+ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
int Q; cin>>Q;
while(Q--)
{
int l1,r1,l2,r2;
scanf("%d %d %d %d",&l1,&r1,&l2,&r2);
double sum=ans[r1][r2]-ans[l1-1][r2]-ans[r1][l2-1]+ans[l1-1][l2-1];
printf("%.10lf\n",sum/(r1-l1+1)/(r2-l2+1));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6396kb
input:
5 7 0 3 3 0 7 -3 3 -7 0 6 1 1 3 3 3 3 4 4 1 1 5 5 5 5 2 2 2 2 4 4 1 5 1 5
output:
24.0000000000 20.4403065089 20.0000000000 19.0000000000 15.4403065089 21.6065716450
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 6480kb
input:
3 186 689 716 695 247 -231 133 1 2 1 3 1 3 2 2 3 3 2 2 2 2 3 3 1 2 1 2 1 2 3 3 1 3 3 3 2 3 3 3 2 2 3 3 1 3 2 2 1 2 3 3 1 2 2 2 1 1 3 3 1 2 1 2 1 1 1 2 1 2 2 2 3 3 2 3 2 2 2 3 1 3 1 3 2 3 1 3 1 2 1 3 1 2 1 2 1 2 2 2 3 3 1 2 1 2 1 3 2 2 1 2 2 2 1 2 1 2 1 3 1 2 1 3 1 3 2 2 1 3 1 2 3 3 1 3 3 3 2 2 1 3 2...
output:
1810.0252312113 1829.3546584226 1452.0540260337 1452.0540260337 1960.0166929831 1510.0423076676 1698.6926238621 1764.0236411424 1452.0540260337 1829.3546584226 1510.0423076676 2018.0049746171 1568.0305893016 1960.0166929831 1902.0284113492 2018.0049746171 1764.0236411424 1764.0236411424 1772.9143620...
result:
ok 133 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 6448kb
input:
3 995 866 -744 999 -528 -207 133 1 2 2 3 2 3 2 3 1 2 2 3 1 2 1 3 1 2 3 3 2 2 2 2 1 3 1 3 3 3 3 3 1 1 2 3 3 3 3 3 1 3 1 1 1 1 3 3 1 2 2 3 2 3 1 2 1 3 1 1 3 3 2 3 1 1 2 3 2 3 1 3 1 2 1 3 1 1 2 2 1 3 1 3 1 1 1 2 1 1 3 3 1 3 1 1 2 2 1 2 2 2 1 3 1 2 1 3 1 2 2 3 2 3 2 2 1 3 1 2 1 2 2 3 1 3 2 3 2 3 1 2 1 3...
output:
3288.1857950114 3607.1024393287 3288.1857950114 3327.8342392698 3288.1857950114 3488.1571065535 3363.2694219717 3726.0477721038 3028.7418170817 3726.0477721038 3261.1771354224 2969.2691506942 3288.1857950114 3288.1857950114 3261.1771354224 3666.5751057163 3028.7418170817 3414.3155652464 3327.8342392...
result:
ok 133 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 6396kb
input:
3 -630 864 896 -31 -359 -691 133 1 3 1 2 1 2 1 2 2 3 2 3 1 2 2 2 1 3 1 3 2 3 2 2 1 3 1 3 1 2 1 1 1 2 1 1 1 2 2 2 1 1 1 3 1 2 1 2 2 2 1 2 2 2 2 3 2 2 2 2 3 3 1 2 1 1 3 3 2 3 1 2 3 3 1 2 1 2 2 3 2 2 2 3 1 2 3 3 2 3 1 3 2 3 2 3 1 2 1 3 1 2 1 3 3 3 2 3 3 3 2 3 2 3 1 3 1 2 1 2 2 3 1 3 3 3 2 2 2 3 1 2 1 2...
output:
3267.2975601703 3267.2975601703 3347.5339322107 3267.2975601703 3255.0284613357 3442.8630629865 3255.0284613357 3267.2975601703 3267.2975601703 3267.2975601703 3240.5521028235 3267.2975601703 3267.2975601703 3442.8630629865 3538.1921937622 3267.2975601703 3187.0611881298 3267.2975601703 3267.2975601...
result:
ok 133 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 6396kb
input:
7 342 -176 53 -703 -687 -627 -580 -95 741 -873 249 47 125 -989 133 2 3 7 7 1 6 1 2 3 6 2 5 4 5 5 7 6 7 3 3 2 4 2 3 1 4 2 5 1 6 1 5 4 5 3 5 1 4 3 3 1 4 1 7 6 7 1 4 3 7 4 5 6 7 2 5 1 5 1 7 1 2 4 6 6 6 1 2 1 3 1 6 3 7 5 7 1 3 1 5 3 7 3 6 2 6 2 5 1 5 2 4 3 4 1 5 3 5 1 2 4 7 3 7 5 7 1 3 3 6 2 6 2 6 2 6 2...
output:
2123.5654111090 2157.7662599915 2486.7414907458 2518.4688725726 2347.0683758134 2368.4242335419 2383.9799238214 2365.0580037650 2551.1004855317 2576.9537396779 2309.5957367223 2227.3389482150 2535.6024323304 2336.3983736128 2349.3367058682 2289.8413315992 2087.1114824953 2272.0273840338 2423.4235397...
result:
ok 133 numbers
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 6400kb
input:
7 105 906 969 -998 68 -422 154 -468 558 785 -849 652 -949 181 133 4 7 2 5 1 6 5 7 5 6 2 7 4 5 4 6 1 4 1 6 2 2 5 7 4 5 4 5 4 6 4 6 6 7 1 6 2 3 3 5 5 7 3 5 6 7 1 6 1 4 3 7 1 6 1 7 3 5 7 7 1 2 2 7 2 5 1 2 4 5 4 5 4 5 3 4 1 6 1 2 5 7 1 2 1 4 1 5 1 5 2 4 4 4 6 7 5 7 2 4 4 4 5 6 3 6 1 4 1 5 5 5 6 7 5 6 3 ...
output:
3419.2323653778 3812.2374749971 3817.7880621641 3368.6827761322 3511.1669182155 3523.7489861640 3124.9801152153 3648.2796487240 3922.0112834559 3390.0738425731 3482.0587339734 3922.0112834559 3420.2688398067 3640.1971568362 3541.9374879458 3822.5463704346 3785.7492931594 3124.9801152153 2934.7040796...
result:
wrong answer 1st numbers differ - expected: '3419.3706440', found: '3419.2323654', error = '0.0000404'