QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735400 | #9289. 1%-Euclidean | N_z_ | WA | 1479ms | 7344kb | C++23 | 6.6kb | 2024-11-11 19:43:31 | 2024-11-11 19:43:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct time_helper{
#ifdef LOCAL
clock_t time_last;time_helper(){time_last=clock();}void test(){auto time_now=clock();std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl;time_last=time_now;}~time_helper(){test();}
#else
void test(){}
#endif
}time_helper;
#ifdef LOCAL
#include"dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
int print_precision=10;bool print_T_endl=1;char print_between=' ';
template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader;struct Writer;template<size_t id>struct read_tuple{template<typename...T>static void read(Reader&stream,std::tuple<T...>&x){read_tuple<id-1>::read(stream,x);stream>>get<id-1>(x);}};template<>struct read_tuple<0>{template<typename...T>static void read([[maybe_unused]]Reader&stream,[[maybe_unused]]std::tuple<T...>&x){}};template<size_t id>struct print_tuple{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){print_tuple<id-1>::print(stream,x);putchar(print_between);stream<<get<id-1>(x);}};template<>struct print_tuple<1>{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){stream<<get<0>(x);}};template<>struct print_tuple<0>{template<typename...T>static void print([[maybe_unused]]Writer&stream,[[maybe_unused]]const std::tuple<T...>&x){}};
struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename...T>Reader&operator>>(std::tuple<T...>&x){read_tuple<sizeof...(T)>::read(*this,x);return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}template<typename T1,typename T2>Reader&operator>>(std::pair<T1,T2>&x){*this>>x.first>>x.second;return *this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';
struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(const T&x){for(auto q:x){*this<<q;if(!is_class<decltype(q)>::value)*this<<print_between;}if(!is_class<typename T::value_type>::value&&print_T_endl)*this<<'\n';return *this;}template<typename...T>Writer&operator<<(const std::tuple<T...>&x){print_tuple<sizeof...(T)>::print(*this,x);if(print_T_endl)*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-print_precision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<print_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<print_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(const T&c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}template<typename T1,typename T2>Writer&operator<<(const std::pair<T1,T2>&x){*this<<x.first<<print_between<<x.second;if(print_T_endl)*this<<'\n';return *this;}Writer&operator<<(const std::string&str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<class Fun>class y_combinator_result{Fun fun_;public:template<class T>explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}template<class ...Args>decltype(auto) operator()(Args &&...args){return fun_(std::ref(*this), std::forward<Args>(args)...);}};template<class Fun>decltype(auto) y_combinator(Fun &&fun){return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));}
void init();void solve(int tc);
main()
{
init();int t=1;
// cin>>t;
for(int tc=1;tc<=t;tc++)solve(tc);
}
void init()
{
}
constexpr int lim=1e8,nlim=1e4;
mt19937 mt(random_device{}());
void solve([[maybe_unused]]int tc)
{
int n;
cin>>n;
vector<pair<int,int>>pt(n);
cin>>pt;
int cnt=0;
double sum=0;
auto sqr=[&](int v){return 1ll*v*v;};
auto getdis=[&](int x,int y){return sqrt(sqr(pt[x].first-pt[y].first)+sqr(pt[x].second-pt[y].second));};
if(n<=nlim)
{
for(int x=0;x<n;x++)
for(int y=0;y<x;y++)
sum+=getdis(x,y),cnt++;
}
else
{
for(int t=0;t<lim;t++)
{
int x=mt()%n,y=mt()%n;
sum+=getdis(x,y),cnt++;
}
}
cout<<sum*n*(n-1)/2/cnt<<endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
3 -1 2 2 2 -1 -2
output:
12.0000000000
result:
ok error = 0.00000 (0.00000e+00)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
4 0 0 2 0 0 2 2 2
output:
13.6568542495
result:
ok error = 0.00000 (3.66117e-11)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
10 -5 -9 5 -1 -8 -7 -6 10 1 -2 -1 -6 -2 3 -3 -1 -5 2 -10 9
output:
447.9360126413
result:
ok error = 0.00000 (6.69782e-13)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3764kb
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:
568237.0112857681
result:
ok error = 0.00000 (2.04871e-16)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3944kb
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:
519539465.9520097374
result:
ok error = 0.00000 (0.00000e+00)
Test #6:
score: 0
Accepted
time: 84ms
memory: 3960kb
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:
520589035884.6277465820
result:
ok error = 0.00000 (1.17242e-16)
Test #7:
score: 0
Accepted
time: 1010ms
memory: 3916kb
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:
520955820046975.1875000000
result:
ok error = -0.00005 (-4.94818e-05)
Test #8:
score: 0
Accepted
time: 1430ms
memory: 7332kb
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...
output:
130346164132638848.0000000000
result:
ok error = 0.00005 (5.03924e-05)
Test #9:
score: 0
Accepted
time: 1479ms
memory: 7220kb
input:
500000 3 8 -4 -10 6 7 5 -8 -4 4 2 8 -7 4 -10 -5 -9 -1 -7 9 7 10 3 5 2 -4 -10 -10 3 0 -3 7 -2 -9 8 4 -5 -6 2 -9 10 -4 9 4 3 -2 -6 8 0 8 -5 -9 -3 10 -9 -3 -7 -9 -7 8 -3 1 -1 -8 -9 7 -9 7 -5 0 -1 -1 -3 9 -2 -6 -5 1 7 -4 -4 5 7 5 -8 5 4 -2 6 8 6 6 4 -10 -7 -5 7 10 10 2 9 -4 -3 -6 1 9 -1 -10 -1 9 1 1 -10...
output:
1366943800320.2822265625
result:
ok error = -0.00002 (-1.63710e-05)
Test #10:
score: 0
Accepted
time: 1382ms
memory: 7220kb
input:
500000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0.0000000000
result:
ok error = 0.00000 (0.00000e+00)
Test #11:
score: 0
Accepted
time: 1410ms
memory: 7252kb
input:
500000 -1000000 -1000000 -1000000 -1000000 1000000 1000000 1000000 1000000 -1000000 -1000000 -1000000 -1000000 -1000000 -1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 -1000000 -1000000 1000000 1000000 -1000000 -1000000 1000000 1000000 1000000...
output:
176802409197752640.0000000000
result:
ok error = 0.00015 (1.45377e-04)
Test #12:
score: 0
Accepted
time: 1409ms
memory: 7344kb
input:
500000 -70213 -71203 -61054 -79198 -95941 28199 -11770 99304 18752 98225 73256 68069 -88777 46027 -67547 73738 -87962 -47566 48747 87313 32574 94545 93353 -35849 -97310 -23035 92492 38013 -59278 -80535 -27784 -96062 47366 88070 -21221 97722 79500 -60660 -82446 56590 19991 97981 -89590 44424 85179 52...
output:
15920625281210170.0000000000
result:
ok error = 0.00005 (5.46009e-05)
Test #13:
score: 0
Accepted
time: 1407ms
memory: 7288kb
input:
500000 -6858 -7277 2327 -9725 -5846 -8113 -5662 -8242 3573 -9339 -9999 90 -1601 9870 9875 -1571 7589 6511 -5146 -8573 -1281 -9917 4273 -9040 -4928 -8701 6890 -7247 -5057 -8626 9204 3908 6224 7826 -8209 5709 -7024 -7117 5797 8148 2480 9687 -8405 5416 -7298 6835 -4742 -8804 8882 -4594 -9285 3712 -4701...
output:
1596283507605116.2500000000
result:
ok error = -0.00006 (-5.97180e-05)
Test #14:
score: 0
Accepted
time: 1419ms
memory: 7216kb
input:
500000 -985 -166 840 -542 -303 -952 -514 -857 -170 985 -888 -458 999 -22 171 985 -997 73 937 347 -474 880 52 -998 482 875 -999 18 -465 -885 -998 54 987 -157 -992 -124 998 48 -826 563 -604 -796 971 238 904 -427 -820 571 935 352 189 981 487 873 -974 -226 987 -155 -72 997 418 -908 192 981 660 -750 881 ...
output:
164048352492706.1250000000
result:
ok error = 0.00002 (1.90261e-05)
Test #15:
score: 0
Accepted
time: 1421ms
memory: 7304kb
input:
500000 64 -76 39 91 -99 12 99 12 99 -8 96 27 8 -99 -83 -55 93 -35 -36 -93 -7 99 -19 98 49 86 99 -9 99 4 -99 -9 54 -84 68 -72 83 55 -95 30 97 -23 -10 99 99 8 -96 -27 -99 -6 29 -95 15 -98 -87 -49 68 -73 -88 -46 99 -4 -88 -46 40 91 -60 -79 47 -88 -47 88 93 -36 -91 -40 98 19 -31 94 -78 62 27 -96 -80 -59...
output:
20886092550731.9687500000
result:
ok error = 0.00376 (3.75857e-03)
Test #16:
score: -100
Wrong Answer
time: 1420ms
memory: 7216kb
input:
500000 9 -4 8 -5 -9 1 3 -9 3 9 -2 9 -9 3 7 -7 -7 6 5 -8 -9 0 0 -9 0 -9 6 -7 0 9 1 -9 0 -9 9 -3 -1 9 -9 1 0 -9 -9 0 -9 -2 8 5 -5 -8 -9 1 8 -5 -9 -3 -8 4 2 -9 -9 2 -8 -4 2 9 -8 5 -1 -9 -3 -9 4 -9 8 5 -4 8 8 5 4 8 2 -9 -3 9 -3 9 -6 7 0 9 9 -3 9 -3 -8 -5 3 9 -9 0 -1 -9 -7 6 1 9 -7 6 4 8 -6 7 1 9 9 2 -9 ...
output:
6393851798664.5078125000
result:
wrong answer error = -0.01220 (-1.21990e-02)