QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#731986 | #393. Signaling | TheZone | 100 ✓ | 173ms | 4524kb | C++20 | 2.2kb | 2024-11-10 12:37:58 | 2024-11-10 12:38:02 |
Judging History
answer
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=3005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
int res=1;
while(n){
if(n&1) res=res*a%mod;
a=a*a%mod;n>>=1;
}
return res;
}
const int iroot=power(3,mod-2);
const int base=131;
double PI = acos(-1.0);
struct vec{
int x=0,y=0;
double d;
vec(int x=0,int y=0):x(x),y(y){
d=atan2(y,x);
}
bool operator<(vec a){
return d<a.d;
}
}P[2*maxn];
int n,X[maxn],Y[maxn];
int total=0;
void solve(){
cin >> n;
for(int i=1;i<=n;i++) cin >> X[i] >> Y[i];
int num=0;
for(int t=1;t<=n;t++){
for(int i=1;i<t;i++) P[i]=vec(X[i]-X[t],Y[i]-Y[t]);
for(int i=t+1;i<=n;i++) P[i-1]=vec(X[i]-X[t],Y[i]-Y[t]);
sort(P+1,P+n);
int B=0;
for(int i=1;i<n;i++){
P[i+n-1]=P[i];
P[i+n-1].d+=2*PI;
}
for(int i=1,j=1;i<n;i++){
while(P[i].d+PI>P[j].d) B++,j++;
num+=(B-1)*(n-1-B);B--;
}
}
num/=2;
int k=num-(n*(n-1)*(n-2)*(n-3)/12);
num=(num-3*k)/2;
int cnt=n*(n-1)*(n-2)/6;
total+=num*2+k;
double ans=3+(double)total/cnt;
cout << setprecision(10) << fixed << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;//cin >> test;
while(test--) solve();
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 4372kb
input:
10 -50 46 12 -45 -75 -9 63 -90 -55 58 34 -93 12 -56 -39 -92 -94 2 -97 56
output:
5.9166666667
result:
ok found '5.91667', expected '5.91667', error '0.00000'
Test #2:
score: 10
Accepted
time: 1ms
memory: 4420kb
input:
20 -92 -19 54 50 -73 8 31 99 -87 77 100 -23 27 71 70 47 -66 -61 -95 51 -69 -35 -72 22 -77 -54 -68 53 50 -32 -43 -42 3 59 -95 3 -7 -2 -43 -64
output:
10.3833333333
result:
ok found '10.38333', expected '10.38333', error '0.00000'
Test #3:
score: 10
Accepted
time: 1ms
memory: 4512kb
input:
50 -453 9273 8635 5374 7799 -7270 4790 5371 -4527 7088 -5703 116 1861 413 4233 -8269 -806 -6547 2147 -6368 6555 -7298 56 -2857 2201 7138 938 7735 -5991 3010 -2957 382 -8048 2456 449 -9863 -9972 8117 558 7923 -9198 -9065 -8252 5549 -7689 939 -3073 -9730 5708 -8504 -3763 -9209 7681 2139 5616 -4776 280...
output:
23.3177551020
result:
ok found '23.31776', expected '23.31775', error '0.00000'
Test #4:
score: 10
Accepted
time: 1ms
memory: 4440kb
input:
100 -2141 -4880 -9922 -5732 -1447 6911 -1075 -6956 -6494 -3573 8708 6799 4213 2423 6020 -1331 8680 4477 -8039 -2826 -7634 -528 -2889 -9898 4520 -6714 -2444 -4444 1162 1172 -2956 -6434 -8580 4504 -4828 837 7455 6831 -3319 2977 6809 -6073 7342 4840 6805 -1347 6238 6681 -1140 7819 6874 3130 -1002 -9025...
output:
44.2391898578
result:
ok found '44.23919', expected '44.23919', error '0.00000'
Test #5:
score: 10
Accepted
time: 3ms
memory: 4504kb
input:
200 -1122 14370 -42358 19597 -8142 -62821 -96727 50998 -39983 -1255 -9889 -32277 -76715 -26038 56558 30000 40878 -16623 -48090 -48731 15995 -5641 75446 -54677 63957 10714 -73685 58774 -51402 -9966 43245 13215 64833 62221 -33150 -97182 -57948 -30006 -39542 -59193 75510 70480 54803 6772 -20806 -42135 ...
output:
86.1282945028
result:
ok found '86.12829', expected '86.12829', error '0.00000'
Test #6:
score: 10
Accepted
time: 15ms
memory: 4456kb
input:
450 311476 420680 -179437 -453868 692958 -289805 882929 -536362 -635778 -76866 -452292 737474 -319376 -97126 -436325 -624165 -830541 -235691 -32100 -25859 269774 -319553 -952967 -665867 -759030 -379696 -799622 531046 162770 929102 959448 -820442 -696548 250017 315619 869226 -950422 483601 -238243 92...
output:
193.1812085057
result:
ok found '193.18121', expected '193.18121', error '0.00000'
Test #7:
score: 10
Accepted
time: 18ms
memory: 4524kb
input:
500 901932 -831127 177611 -452336 -81615 -260260 -868737 915377 -805269 -567574 -621357 -983383 -478831 -753449 -146546 929599 -705635 256170 55217 -697919 -708568 -316283 720771 -686336 568982 851708 569161 638609 -641368 -750581 -247391 301211 -342708 673355 393219 -184972 -676469 154890 -559945 8...
output:
213.6206740227
result:
ok found '213.62067', expected '213.62067', error '0.00000'
Test #8:
score: 10
Accepted
time: 75ms
memory: 4472kb
input:
1000 618441 536922 -670652 756937 -951203 -88976 -96750 102377 -49403 267613 -202790 492478 328782 -572207 -401320 -225835 -533681 -451907 298806 -554354 -933347 -292249 -396171 -911579 -211258 458880 60941 -128449 -856581 -816717 -782661 221946 219834 -400346 531242 -745577 -789282 -735078 253598 5...
output:
424.1060140581
result:
ok found '424.10601', expected '424.10601', error '0.00000'
Test #9:
score: 10
Accepted
time: 173ms
memory: 4428kb
input:
1500 -466267 -545644 842097 -947922 699094 -376679 708277 42478 712256 813305 -629139 377724 795013 -265652 885435 362587 105505 -151452 419402 618775 -824399 431939 936446 382165 -227899 -244470 476667 778569 -349480 729226 -248801 -328251 -829799 -147620 270009 -822539 -760492 814759 -278341 -5627...
output:
636.5350248060
result:
ok found '636.53502', expected '636.53503', error '0.00000'
Test #10:
score: 10
Accepted
time: 169ms
memory: 4424kb
input:
1500 372361 -892254 674948 369064 663890 427706 -962493 -748469 -296124 -837649 366715 89587 414772 -877335 -788861 594332 -306600 -691 -443204 -140585 325874 -187797 -549930 -649347 -689284 -598867 -174278 921052 -691067 551110 -491282 -305052 439793 -153742 858640 165072 141049 845958 -974583 3462...
output:
637.3585487272
result:
ok found '637.35855', expected '637.35855', error '0.00000'