QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#451142 | #142. 平面最近点对 | hos_lyric | 0 | 1ms | 4132kb | C++14 | 2.6kb | 2024-06-22 21:29:58 | 2024-06-22 21:29:59 |
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%