QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#451142#142. 平面最近点对hos_lyric0 1ms4132kbC++142.6kb2024-06-22 21:29:582024-06-22 21:29:59

Judging History

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

  • [2024-06-22 21:29:59]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4132kb
  • [2024-06-22 21:29:58]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


using Pt = pair<Int, Int>;
#define x first
#define y second

Int sq(Int r) {
  return r * r;
}

int N;
vector<Pt> P;

Int R2;
void check(const Pt &p, const Pt &q) {
  chmin(R2, sq(p.x - q.x) + sq(p.y - q.y));
}

vector<Pt> ps, qs;
void rec(int l, int r) {
  if (l + 1 < r) {
    const int m = (l + r) / 2;
    const Int xMid = P[m].x;
    rec(l, m);
    rec(m, r);
    const Int R = sqrt((long double)R2);
    int psLen = 0, qsLen = 0;
    for (int u = l; u < m; ++u) if (xMid - P[u].x < R) ps[psLen++] = P[u];
    for (int u = m; u < r; ++u) if (P[u].x - xMid < R) qs[qsLen++] = P[u];
    for (int i = 0, j0 = 0, j1 = 0; i < psLen; ++i) {
      for (; j0 < qsLen && qs[j0].y <= ps[i].y - R; ++j0) {}
      for (; j1 < qsLen && qs[j1].y <  ps[i].y + R; ++j1) {}
      for (int j = j0; j < j1; ++j) {
        check(ps[i], qs[j]);
      }
    }
    inplace_merge(P.begin() + l, P.begin() + m, P.begin() + r, [&](const Pt &p, const Pt &q) -> bool {
      return (p.y < q.y);
    });
  }
}

int main() {
  for (; ~scanf("%d", &N); ) {
    P.resize(N);
    for (int u = 0; u < N; ++u) {
      scanf("%lld%lld", &P[u].x, &P[u].y);
    }
    
    // ?
    assert(N >= 2);
    
    sort(P.begin(), P.end());
    R2 = 9001001001001001001LL;
    ps.resize(N);
    qs.resize(N);
    rec(0, N);
    printf("%.15f\n", sqrt((double)R2));
  }
  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: 3992kb

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.828427124746190

result:

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

Test #2:

score: 0
Accepted
time: 1ms
memory: 4096kb

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.602325267042627

result:

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

Test #3:

score: 0
Accepted
time: 0ms
memory: 4108kb

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.142135623730951

result:

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

Test #4:

score: 0
Accepted
time: 1ms
memory: 4068kb

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.485281374238570

result:

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

Test #5:

score: 0
Accepted
time: 1ms
memory: 4000kb

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.236067977499790

result:

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

Test #6:

score: 0
Accepted
time: 1ms
memory: 4108kb

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.000000000000000

result:

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

Test #7:

score: 0
Accepted
time: 1ms
memory: 4048kb

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.071067811865476

result:

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

Test #8:

score: 0
Accepted
time: 1ms
memory: 4048kb

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:

10.198039027185569

result:

ok found '10.1980390', expected '10.1980390', error '0.0000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 4048kb

input:

2905
5544 16176
11504 10282
2559 25147
13685 28854
22579 1388
17317 1984
6352 11519
7336 2667
1316 1562
2609 7357
7088 14893
9314 17654
8800 27115
14676 25451
27421 25801
14436 10942
18523 25981
8686 16405
9068 26827
19020 9730
22399 23805
19890 935
17751 418
12577 8081
21912 26733
8184 2548
3106 57...

output:

6.403124237432849

result:

ok found '6.4031242', expected '6.4031242', error '0.0000000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3988kb

input:

2913
11370 12601
5375 12389
19018 10607
13570 24071
14694 4758
24116 28315
8846 9892
5535 6561
19331 24958
4453 11136
17257 13976
18700 25978
12828 5326
18400 2999
28598 12038
11237 24265
19317 23350
23606 1097
17475 28271
14115 3082
19230 15682
11040 22141
1420 22549
4899 19979
3065 11184
3747 1800...

output:

5.830951894845301

result:

ok found '5.8309519', expected '5.8309519', error '0.0000000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4048kb

input:

2901
5137 5191
14939 18114
686 17953
6125 13559
12280 1161
15748 8778
17324 19812
8066 3377
2005 2060
8279 4712
7962 15638
14804 20785
15838 27468
16022 20920
25191 25886
6271 4511
4454 15500
20878 22558
3180 25018
19403 25897
21777 27083
12010 11560
10476 264
26322 19410
18624 17218
10503 20845
259...

output:

7.615773105863909

result:

ok found '7.6157731', expected '7.6157731', error '0.0000000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 4108kb

input:

2967
21729 13901
14984 631
9715 1243
12044 14302
14184 8687
20119 29500
1630 1679
9252 12762
10333 27445
7692 14205
24226 26191
21430 12595
9680 15025
21082 26361
14265 17819
25234 10290
13284 12284
20496 7051
21080 11310
4705 10426
17813 642
21653 24564
2062 8482
24447 20009
10529 13105
12674 26203...

output:

8.485281374238570

result:

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

Test #13:

score: 0
Accepted
time: 1ms
memory: 4044kb

input:

2950
7362 24422
1860 4478
4410 20906
17675 28679
22144 9650
13906 9626
3575 6716
25789 8384
21148 22996
26367 9570
7556 6448
3779 18005
22189 19415
5862 29338
21366 15894
12941 13944
193 16242
11933 16827
11801 21990
18316 7782
4360 6788
25496 6710
18676 20844
4232 6605
23089 7720
17360 16692
24024 ...

output:

10.049875621120890

result:

ok found '10.0498756', expected '10.0498756', error '0.0000000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

2917
3911 20228
26229 16985
6337 20601
13694 9726
10128 10943
25677 25223
25291 5475
11046 1831
13363 24845
8261 15776
19724 13227
7003 15308
10691 2884
6642 24024
19525 4190
19255 9234
19616 18420
11638 11857
7321 9586
2771 24180
16225 27275
15413 19921
13640 7909
4185 5680
26864 9599
11633 13331
2...

output:

4.000000000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

2953
6440 27024
3143 7572
12164 9883
7992 20360
12891 27207
8893 26234
27208 23549
26161 17785
1612 5621
23610 25805
23114 20452
22679 5627
3161 20418
3125 14236
8205 22564
22236 20417
7014 2299
14401 13890
10192 764
25652 11079
8545 25856
8699 6659
24623 16136
27334 5021
28502 14724
5868 16745
8891...

output:

7.810249675906654

result:

ok found '7.8102497', expected '7.8102497', error '0.0000000'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4124kb

input:

2936
7212 5833
853 20043
14934 21745
319 19625
17764 3072
18093 27900
16870 17341
24195 5935
5277 8550
16626 24384
22923 5768
28137 14009
2962 19530
27438 19854
1497 7607
17108 21621
12092 24625
11541 23149
16404 9327
21561 8404
21344 14713
3743 16350
8421 15840
24854 16508
3839 20418
14548 10571
10...

output:

8.944271909999159

result:

ok found '8.9442719', expected '8.9442719', error '0.0000000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4128kb

input:

2922
11867 22431
23784 23207
2701 6297
23091 23564
8208 23903
9411 16139
3518 12786
6372 16353
6684 6476
13858 19707
12823 14107
27785 2315
27248 29215
5369 26980
15845 5189
19775 21600
14293 14306
14340 13448
17993 8321
6603 4172
1557 9774
15417 6388
27265 26863
10964 4618
2999 17351
27003 7129
218...

output:

12.206555615733702

result:

ok found '12.2065556', expected '12.2065556', error '0.0000000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 4052kb

input:

2980
11254 1334
9778 19499
5121 24775
29371 1215
805 9394
25571 19604
14056 21077
9645 25856
16724 12217
8736 4014
4255 20515
25600 14975
26486 11497
19932 26496
23823 5450
12240 3428
5545 22019
10851 26015
2979 19067
13271 9885
7252 6620
654 4326
7651 10957
3676 5901
17583 29234
3595 12212
5593 222...

output:

6.324555320336759

result:

ok found '6.3245553', expected '6.3245553', error '0.0000000'

Test #19:

score: 0
Accepted
time: 1ms
memory: 4132kb

input:

2917
3367 18980
23528 8138
27340 9571
19491 4017
6977 23850
26904 12719
25057 24981
3293 27877
6044 20776
25826 18719
14878 18848
18735 24895
3470 23564
19814 15277
8987 1356
9738 21252
20411 16713
14956 1183
4529 19278
14971 26277
27852 8264
14382 15808
24888 15254
24451 7534
25957 20715
18641 6484...

output:

5.385164807134504

result:

ok found '5.3851648', expected '5.3851648', error '0.0000000'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4120kb

input:

2995
7906 1744
9243 6420
15669 14807
9731 21221
12244 2360
1559 10270
11032 2541
29796 12578
14944 11651
492 3865
17644 1699
25261 15215
11454 8869
4798 11221
18260 17579
16377 27554
9921 2894
16002 14046
20837 11352
8951 17198
1590 2548
12262 2823
2830 13661
25604 11582
7317 28810
16910 20993
8851 ...

output:

2.236067977499790

result:

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

Test #21:

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

input:

2916
2659 12063
29048 3837
12921 16927
25369 1985
21936 9274
838 12881
25577 15592
17029 27951
27320 25494
5664 24546
7520 10863
12037 25591
12285 20504
19922 13943
10733 18874
15986 27043
17442 21827
1068 20502
24938 28643
9385 11729
26704 3574
13177 15579
8068 19073
23256 19983
7753 15282
11061 32...

output:

8.246211251235321

result:

wrong answer 1st numbers differ - expected: '8.0622577', found: '8.2462113', error = '0.0228166'

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%