fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int maxn = 1e5 + 5;
  7. int p[maxn];
  8. pair<int, int> points[maxn];
  9. int comp = 0;
  10.  
  11. int Find(int x) {
  12. if (x == p[x]) {
  13. return x;
  14. }
  15. return p[x] = Find(p[x]);
  16. }
  17.  
  18. void Union(int a, int b) {
  19. int ra = Find(a);
  20. int rb = Find(b);
  21. if (ra != rb) {
  22. p[ra] = rb;
  23. --comp;
  24. }
  25. }
  26.  
  27. inline bool InRange(int i, int j, ll d) {
  28. ll dx = (ll)(points[j].first - points[i].first);
  29. ll dy = (ll)(points[j].second - points[i].second);
  30.  
  31. // Not use sqrt here.
  32. return dx * dx + dy * dy <= d * d;
  33. }
  34.  
  35. int main() {
  36. ios_base::sync_with_stdio(0);
  37. cin.tie(0);
  38.  
  39. int n;
  40. ll d;
  41.  
  42. iota(p, p + maxn, 0);
  43. cin >> n >> d;
  44. comp = n;
  45. for (int i = 0; i < n; ++i) {
  46. auto& [x, y] = points[i];
  47. cin >> x >> y;
  48. }
  49. sort(points, points + n);
  50. for (int i = 0; i < n; ++i) {
  51. int j;
  52. for (j = i - 1; j >= 0; --j) {
  53. if (points[i].first - points[j].first > d) {
  54. break;
  55. }
  56. }
  57. for (int k = i - 1; k > j; --k) {
  58. if (InRange(k, i, d)) {
  59. Union(k, i);
  60. }
  61. }
  62. }
  63. cout << comp << '\n';
  64.  
  65. return 0;
  66. }
Success #stdin #stdout 0.01s 5284KB
stdin
944 41
915 498
252 522
178 275
830 87
164 894
794 538
331 304
457 310
758 260
796 679
358 677
892 307
344 399
232 403
143 850
845 606
206 489
648 934
608 757
654 228
334 184
889 300
417 744
456 850
907 772
925 954
540 246
527 602
600 646
564 637
325 147
74 831
238 204
638 634
592 146
989 164
783 671
167 868
926 245
249 863
462 658
900 499
757 694
907 221
74 438
806 199
314 41
654 707
932 639
232 161
93 993
214 541
420 969
767 228
442 411
420 730
316 56
664 126
838 199
980 802
139 297
17 507
455 9
198 86
51 351
534 941
133 241
783 290
63 136
765 32
749 297
189 318
236 578
809 818
868 486
994 374
776 66
445 939
692 653
524 49
481 246
140 104
532 790
321 697
423 90
934 278
517 498
660 143
702 9
871 698
413 430
958 978
583 106
672 352
773 655
733 778
784 882
551 687
824 265
983 330
628 560
672 636
159 153
936 754
784 813
165 423
218 406
960 202
416 689
85 396
256 854
685 809
429 801
503 522
629 76
291 55
919 600
854 29
426 296
205 763
76 711
733 152
697 809
978 9
232 464
941 140
628 15
66 305
894 810
861 371
909 879
170 577
61 398
831 909
995 466
932 89
190 473
295 339
754 377
41 323
222 251
338 54
994 535
176 107
395 986
472 396
444 736
533 824
927 140
576 651
96 165
882 276
438 776
48 383
279 218
952 47
232 90
275 631
435 295
359 732
448 408
337 921
216 293
421 696
73 567
875 477
881 811
651 960
418 696
932 508
502 829
779 705
92 137
849 847
497 524
554 71
282 160
98 554
305 490
559 954
15 883
398 33
723 881
216 347
121 619
274 316
232 717
468 291
532 239
933 454
623 431
963 320
28 646
206 662
837 262
181 218
134 511
532 443
533 740
732 939
45 383
351 517
908 997
363 981
681 827
444 71
672 185
132 444
618 501
849 430
359 440
883 704
409 724
857 201
385 495
361 637
611 907
491 809
137 392
974 111
878 736
263 792
116 581
497 116
660 102
488 89
893 383
941 697
441 408
0 572
450 549
169 151
847 83
838 140
729 280
384 607
265 393
907 396
229 925
271 412
605 341
473 794
49 212
45 126
862 716
387 87
802 324
641 672
80 737
830 179
442 250
47 134
448 371
157 891
652 148
161 213
108 530
843 288
571 952
154 670
820 986
897 720
583 182
559 991
499 247
961 51
31 188
994 739
638 64
642 706
229 530
805 318
356 636
405 244
529 774
873 529
752 241
855 347
685 255
690 861
990 26
462 622
623 861
599 487
810 793
19 943
37 368
201 77
759 17
878 211
296 706
424 410
485 671
693 204
248 579
254 507
634 459
435 744
454 650
777 424
496 432
559 310
0 689
842 961
890 370
870 222
6 722
399 717
670 773
278 207
784 716
493 948
521 617
667 131
526 412
251 809
10 68
103 901
436 134
631 126
481 396
380 469
941 895
739 263
531 241
541 599
333 15
212 622
95 218
155 340
636 721
985 953
115 307
917 590
445 948
838 971
206 202
598 471
899 165
308 442
841 473
788 332
584 402
219 839
902 443
972 521
420 213
460 896
81 708
619 583
509 689
950 546
57 301
779 384
265 590
400 816
522 855
931 828
929 936
313 740
615 931
230 281
568 412
609 442
557 143
950 590
827 200
114 642
992 319
172 202
695 490
674 322
456 190
112 524
981 336
493 888
847 771
575 629
621 738
794 894
642 730
840 485
921 432
976 408
831 832
697 445
136 464
961 455
515 918
687 193
910 67
774 154
679 625
815 755
612 602
831 482
423 997
440 259
734 221
135 298
228 646
952 194
505 446
891 141
378 512
358 136
544 627
318 382
458 27
728 391
220 257
191 528
305 827
655 309
583 889
782 602
873 586
174 985
189 688
793 326
441 403
877 946
390 248
769 241
417 418
918 409
612 357
566 917
948 36
714 863
721 4
846 261
667 751
767 193
757 135
72 929
924 342
792 238
14 541
455 94
210 821
209 639
461 38
177 407
304 467
753 30
640 113
612 853
464 890
862 233
734 694
433 295
89 992
16 710
506 673
271 382
605 987
859 332
840 536
314 192
872 618
4 450
271 305
923 537
640 3
605 756
451 77
888 565
649 883
89 869
811 767
442 341
201 243
645 982
738 603
754 172
890 41
521 14
576 996
843 463
166 963
685 868
25 477
406 795
351 127
627 36
130 539
184 10
127 490
120 539
50 399
865 990
650 961
362 136
393 614
222 272
165 277
169 368
428 856
71 316
713 691
547 417
360 219
359 161
718 38
376 868
339 586
278 201
145 852
691 698
592 147
696 672
82 999
126 36
396 628
492 275
904 455
78 771
957 602
748 729
177 387
571 324
560 893
846 887
669 490
511 729
852 604
820 745
517 180
797 42
686 267
403 518
228 480
823 999
994 949
484 668
542 866
331 863
666 328
235 210
435 586
535 517
185 906
725 786
822 274
128 101
693 407
745 172
248 512
349 701
657 243
963 593
952 768
832 573
637 177
464 624
431 949
689 801
740 302
103 559
110 877
221 379
573 470
827 31
601 643
252 223
181 532
274 87
370 821
716 250
305 736
187 153
396 796
586 29
65 109
1 134
379 863
743 256
554 783
807 348
523 756
81 765
359 393
29 564
905 707
192 397
129 836
863 427
280 878
526 541
716 862
731 944
128 227
384 956
587 497
372 602
551 385
741 798
194 900
723 943
628 386
409 198
522 594
709 874
169 460
758 375
688 659
266 377
964 422
280 567
655 26
31 577
910 175
221 181
232 375
848 898
333 29
257 266
268 723
534 538
198 149
57 761
761 274
421 155
433 881
608 391
850 797
260 660
925 776
681 524
36 337
464 296
373 382
388 91
291 385
99 895
662 730
569 661
978 265
457 95
464 567
460 834
462 851
996 965
236 391
556 351
745 428
818 185
817 826
362 796
238 442
799 589
705 408
989 211
396 625
888 71
392 175
475 186
79 12
502 379
219 3
64 145
625 491
253 193
449 811
800 55
360 22
443 863
506 839
100 154
348 52
13 120
710 401
322 932
704 602
57 361
622 353
415 430
343 567
911 961
861 428
734 94
954 151
420 237
885 881
222 227
353 388
934 568
783 263
545 716
765 900
517 235
325 100
781 294
912 273
627 293
902 204
814 802
745 134
494 245
198 678
737 130
539 570
258 90
4 339
272 799
113 487
943 85
589 307
435 980
801 538
208 920
179 233
842 779
873 292
415 521
56 885
100 959
780 772
361 989
302 650
385 599
894 349
443 457
726 460
89 613
55 617
941 472
150 461
866 755
362 466
123 142
898 724
235 943
589 415
72 282
877 116
993 522
985 169
143 244
194 221
483 768
329 941
385 9
138 217
685 27
266 492
633 189
89 56
943 326
125 742
320 965
195 39
547 431
281 172
108 973
205 115
669 973
159 628
338 933
254 955
494 661
61 725
339 725
748 278
193 278
374 601
829 584
361 924
40 425
278 554
52 611
568 174
541 226
582 527
140 520
823 712
856 893
765 674
306 787
239 422
9 664
560 566
489 824
285 714
938 387
48 367
847 866
391 44
751 401
928 91
846 316
722 43
606 461
289 877
657 521
187 959
703 674
965 939
322 682
842 427
865 510
453 49
355 453
826 573
372 854
538 417
794 191
665 941
945 601
102 927
47 489
927 89
854 384
941 536
991 495
390 190
4 12
388 341
586 463
993 631
771 135
266 219
595 468
474 492
998 551
982 22
280 168
191 601
199 217
109 118
884 98
599 595
708 772
932 998
883 990
128 552
451 800
66 433
508 196
558 161
195 93
721 315
268 587
895 985
922 392
872 653
538 696
92 889
554 577
296 632
688 424
832 114
799 202
319 491
206 921
309 416
271 813
64 526
929 557
33 662
484 900
788 829
555 733
829 218
633 976
613 142
10 272
150 990
879 910
376 442
949 230
986 697
494 183
254 311
838 932
595 849
142 66
703 144
438 514
481 532
743 901
653 906
286 181
761 89
652 773
365 674
151 95
843 909
802 527
839 800
733 486
406 104
810 940
974 287
823 126
85 7
737 420
388 732
745 699
887 385
87 599
61 51
835 79
624 287
886 974
843 53
581 994
945 583
53 727
968 394
508 381
85 753
579 694
262 946
455 428
560 706
545 613
675 1
510 127
596 158
579 459
545 719
355 39
261 605
920 269
12 828
221 956
800 774
478 603
909 936
124 425
200 908
99 560
223 559
332 781
111 518
461 679
904 160
601 456
746 756
994 267
680 631
987 210
stdout
32