QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92214#142. 平面最近点对youngsystem#0 3ms3760kbC++1.6kb2023-03-30 14:21:462023-03-30 14:21:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 14:21:48]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:3760kb
  • [2023-03-30 14:21:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
set<pair<int,int> >se;
struct dian
{
	int x,y;
}d[2000005];
bool bi(struct dian c,struct dian d)
{
	if(c.x!=d.x)return c.x<d.x;
	return c.y<d.y;
}
int main()
{
	int n;
	n=read();
	for(int i=1;i<=n;i++)
	{
		d[i].x=read();
		d[i].y=read();
	}
	sort(d+1,d+n+1,bi);
	int nl=1;
	__int128 ans=1;
	for(int i=1;i<=30;i++)ans*=10;
	for(int i=1;i<=n;i++)
	{
		while(nl<i&&(__int128)(d[i].x-d[nl].x)*(d[i].x-d[nl].x)>ans)
		{
			se.erase(make_pair(d[nl].y,nl));
			nl++;
		}
		if(se.empty())
		{
			se.insert(make_pair(d[i].y,i));
			continue;
		}
		set<pair<int,int> >::iterator it=se.lower_bound(make_pair(d[i].y,0));
		for(set<pair<int,int> >::iterator nit=it;nit!=se.end();nit++)
		{
			if((__int128)(nit->first-d[i].y)*(nit->first-d[i].y)>ans)break;
			int now=nit->second;
			ans=min(ans,(__int128)(d[i].x-d[now].x)*(d[i].x-d[now].x)+(__int128)(d[i].y-d[now].y)*(d[i].y-d[now].y));
		}
		for(set<pair<int,int> >::iterator nit=it;;nit--)
		{
			if(nit==se.end())nit--;
			if((__int128)(d[i].y-nit->first)*(d[i].y-nit->first)>ans)break;
			int now=nit->second;
			ans=min(ans,(__int128)(d[i].x-d[now].x)*(d[i].x-d[now].x)+(__int128)(d[i].y-d[now].y)*(d[i].y-d[now].y));
			if(nit==se.begin())break;
		}
		se.insert(make_pair(d[i].y,i));
	}
	printf("%.9Lf\n",sqrt((long double)ans));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 15
Accepted
time: 1ms
memory: 3636kb

input:

2933
19320 28055
2053 27470
14635 1378
27582 9822
28729 107
22351 3093
17670 379
23901 4686
27182 12261
19443 8467
24208 20283
10763 10584
25953 28380
28290 27394
19572 14769
4024 12401
23295 3267
26949 176
13416 4517
23856 15413
26260 18957
18275 24409
999 3873
28202 14686
25446 2822
24009 8949
114...

output:

2.828427125

result:

ok found '2.8284271', expected '2.8284271', error '0.0000000'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3760kb

input:

2912
721 22031
501 17261
11583 2570
25091 26662
7053 8645
13085 13755
15427 10176
10602 28715
16277 17856
9356 11466
5758 16745
4367 27948
15523 3209
27447 13908
24316 27667
11649 8344
9848 2897
219 21503
22524 11664
5725 1460
24127 12567
25935 14858
8457 13415
16347 12044
28163 753
28967 22202
2418...

output:

8.602325267

result:

ok found '8.6023253', expected '8.6023253', error '0.0000000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

2919
2259 8882
27694 23328
12744 20731
7265 21050
9456 6920
13055 18791
28400 8457
16815 27147
17978 11787
8903 7696
17316 10505
28428 15732
15370 9751
23862 25477
5316 5647
24987 27499
11625 15403
27782 4138
9728 5740
18123 13962
2177 7071
27078 7038
4083 2679
28762 5376
16196 6309
2708 25797
23383...

output:

14.142135624

result:

ok found '14.1421356', expected '14.1421356', error '0.0000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3628kb

input:

2998
25897 23111
13024 10321
15964 26479
17278 5912
13799 21852
20180 4213
27326 12582
1533 11852
16882 2495
528 13201
21465 18041
540 4999
28233 3336
9986 1089
6821 20255
3089 17725
4583 22110
3588 8106
25230 22362
18344 2991
26627 13592
29199 19
23076 17065
20627 9037
639 2945
26311 15104
4108 118...

output:

8.485281374

result:

ok found '8.4852814', expected '8.4852814', error '0.0000000'

Test #5:

score: 0
Accepted
time: 3ms
memory: 3756kb

input:

2969
20252 368
21295 919
29391 369
18543 2203
14469 6782
5248 23342
7294 9742
21414 29623
745 21715
26138 28081
29054 22366
17394 24941
17790 16310
9892 3947
25729 28818
27425 15079
21592 28422
12126 2901
10434 25370
6757 24560
1388 2072
22096 2842
13285 18508
13305 8648
10845 17840
10651 19691
1118...

output:

2.236067977

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

2906
2294 19051
9437 28110
3472 25345
22267 17834
15400 6045
12007 5001
27379 24499
15386 10583
10415 18346
14140 8534
16468 6545
22225 132
18670 27325
16117 5289
20838 20510
7406 8688
9684 4688
5594 1497
10942 25637
3335 11901
27199 13109
26244 12524
4495 24312
17605 9663
7320 18280
19337 752
647 8...

output:

3.000000000

result:

ok found '3.0000000', expected '3.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3624kb

input:

2914
4767 25591
11281 25693
15021 8027
13143 18347
12872 16822
3252 25409
22023 365
23139 25813
3372 5371
21880 7390
21400 7290
20972 24123
24122 19495
13975 6046
426 13364
4671 18671
1039 6519
3279 28542
20995 12797
2488 25887
14985 7139
28322 23785
9612 777
4453 26877
3703 5074
21602 1418
5867 123...

output:

7.071067812

result:

ok found '7.0710678', expected '7.0710678', error '0.0000000'

Test #8:

score: -15
Wrong Answer
time: 1ms
memory: 3624kb

input:

2979
7893 7802
20059 24540
20875 24953
2547 12366
467 16268
20147 26084
5925 18991
13710 25946
10693 800
4219 20513
17462 29331
21881 20614
3569 15805
3926 7909
9560 12579
20336 29519
16906 6613
21462 1275
21522 16591
3024 2941
8360 3888
22198 17328
2785 4662
15226 11189
2407 13438
20632 9776
17201 ...

output:

15.620499352

result:

wrong answer 1st numbers differ - expected: '10.1980390', found: '15.6204994', error = '0.5317160'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%