QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#92214 | #142. 平面最近点对 | youngsystem# | 0 | 3ms | 3760kb | C++ | 1.6kb | 2023-03-30 14:21:46 | 2023-03-30 14:21:48 |
Judging History
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%