QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#760420#9289. 1%-EuclideanN_z_WA 1900ms7320kbC++236.7kb2024-11-18 16:53:562024-11-18 16:53:58

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 16:53:58]
  • 评测
  • 测评结果:WA
  • 用时:1900ms
  • 内存:7320kb
  • [2024-11-18 16:53:56]
  • 提交

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=1.25e8,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;
			if(x==y)continue;
			sum+=getdis(x,y),cnt++;
		}
	}
	cout<<sum*n*(n-1)/2/cnt<<endl;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3948kb

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: 3944kb

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: 3828kb

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: 0ms
memory: 3916kb

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: 1ms
memory: 3712kb

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: 87ms
memory: 3956kb

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: 1290ms
memory: 4016kb

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:

520979708026754.0000000000

result:

ok error = -0.00000 (-3.62991e-06)

Test #8:

score: 0
Accepted
time: 1811ms
memory: 7152kb

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:

130344769192152704.0000000000

result:

ok error = 0.00004 (3.96900e-05)

Test #9:

score: 0
Accepted
time: 1802ms
memory: 7320kb

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:

1367024505317.1054687500

result:

ok error = 0.00004 (4.26685e-05)

Test #10:

score: 0
Accepted
time: 1757ms
memory: 7320kb

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: 1805ms
memory: 7260kb

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:

176748606207476832.0000000000

result:

ok error = -0.00016 (-1.58979e-04)

Test #12:

score: 0
Accepted
time: 1820ms
memory: 7208kb

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:

15920098466798650.0000000000

result:

ok error = 0.00002 (2.15091e-05)

Test #13:

score: 0
Accepted
time: 1821ms
memory: 7304kb

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:

1596565879824504.7500000000

result:

ok error = 0.00012 (1.17165e-04)

Test #14:

score: 0
Accepted
time: 1900ms
memory: 7272kb

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:

164099505323727.7500000000

result:

ok error = 0.00033 (3.30848e-04)

Test #15:

score: 0
Accepted
time: 1818ms
memory: 7208kb

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:

20775737989511.2968750000

result:

ok error = -0.00154 (-1.54493e-03)

Test #16:

score: -100
Wrong Answer
time: 1823ms
memory: 7288kb

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:

6544799318473.4472656250

result:

wrong answer error = 0.01112 (1.11212e-02)