QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562283 | #9289. 1%-Euclidean | zjy0001 | TL | 360ms | 11232kb | C++17 | 790b | 2024-09-13 16:28:26 | 2024-09-13 16:28:26 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=5e5+5,B=35;
const ldb pi=acosl(-1);
int n,id[N];ldb s,ans,val[N];pair<int,int>A[N];
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=0;i<n;++i)cin>>A[i].first>>A[i].second;
for(int k=0;k<B;++k){
const ldb x=cosl(pi*k/B),y=-sinl(pi*k/B);
for(int i=0;i<n;++i)val[i]=A[i].first*x+A[i].second*y,id[i]=i;
sort(id,id+n,[&](const int&x,const int&y){return val[x]<val[y];});
s=0;for(int i=0;i<n;++i)ans+=val[id[i]]*i-s,s+=val[id[i]];
s=0;for(int i=n;i--;)ans+=s-val[id[i]]*(n-i-1),s+=val[id[i]];
}
cout<<fixed<<setprecision(10)<<ans*pi/B/4<<'\n';
return 0;
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8152kb
input:
3 -1 2 2 2 -1 -2
output:
11.9977948657
result:
ok error = -0.00018 (-1.83761e-04)
Test #2:
score: 0
Accepted
time: 1ms
memory: 8316kb
input:
4 0 0 2 0 0 2 2 2
output:
13.6559861817
result:
ok error = -0.00006 (-6.35628e-05)
Test #3:
score: 0
Accepted
time: 1ms
memory: 8400kb
input:
10 -5 -9 5 -1 -8 -7 -6 10 1 -2 -1 -6 -2 3 -3 -1 -5 2 -10 9
output:
447.8963605196
result:
ok error = -0.00009 (-8.85218e-05)
Test #4:
score: 0
Accepted
time: 0ms
memory: 8248kb
input:
100 38 5 49 98 51 73 -9 88 85 -17 74 -89 -7 -83 75 -45 -7 -86 -1 -83 64 29 -100 70 94 -31 33 -58 -19 53 -68 -24 -20 -95 -58 -82 96 17 -57 -66 25 -82 33 -88 -30 9 -78 -81 -96 80 -61 98 -70 91 18 -75 -74 -57 -49 46 -30 83 33 -71 97 -36 77 -98 -41 -80 -10 -58 -65 -82 75 -56 71 -99 -79 18 -69 45 85 37 1...
output:
568234.7346927785
result:
ok error = -0.00000 (-4.00641e-06)
Test #5:
score: 0
Accepted
time: 0ms
memory: 8072kb
input:
1000 944 590 -334 904 889 -282 425 -325 -103 -809 993 911 143 443 -932 605 -301 -176 -157 146 -633 -399 -150 955 -363 -14 -817 493 -47 720 -928 -965 -8 -316 272 -299 907 -72 -844 758 642 -52 235 498 -822 204 -224 618 337 55 -809 710 -564 -937 -638 -371 -961 244 -652 408 -298 955 264 -680 -963 -767 -...
output:
519539498.4139651185
result:
ok error = 0.00000 (6.24822e-08)
Test #6:
score: 0
Accepted
time: 28ms
memory: 8272kb
input:
10000 -659 -2844 -8357 -6691 -1461 -3785 -2767 2416 -8822 1703 9241 -2262 -1504 -3990 6987 -5208 2984 -9116 7244 2503 -6187 6720 -1624 -931 6738 -7167 2962 -4352 -6964 -8792 6241 -582 -6450 -1229 2177 -1269 1714 -3459 -7260 -8263 6329 5496 9797 -8972 927 -5671 -2721 3134 9392 5161 -5527 -2240 -983 7...
output:
520589029752.2672142684
result:
ok error = -0.00000 (-1.17797e-08)
Test #7:
score: 0
Accepted
time: 360ms
memory: 11232kb
input:
100000 -83701 75196 45765 -6235 36272 37275 -35366 -82843 8306 -1369 -28173 46051 -65089 -8781 75824 -54559 -55700 -93735 59743 86007 -72405 -47645 24812 35094 -4454 -21204 -35485 87381 28200 45650 904 -80565 38488 14842 10353 48050 66074 7042 61753 71952 55030 -92952 -44662 -94767 -59269 -34289 374...
output:
520981599585595.2998962402
result:
ok error = 0.00000 (8.53286e-10)
Test #8:
score: -100
Time Limit Exceeded
input:
500000 -583904 203313 -340892 -796716 910437 -246461 -246636 206026 -735478 953404 746547 -77553 -661769 967977 -312048 -680490 -776092 95714 140302 677488 -907238 962373 -225267 107163 714274 -295282 430205 384021 -737797 -503077 871316 171099 -234497 -767343 -149102 399526 912881 -921105 -831662 6...