QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#478256#142. 平面最近点对Williamxzh#0 4ms6668kbC++231.6kb2024-07-14 19:41:222024-07-14 19:41:22

Judging History

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

  • [2024-07-14 19:41:22]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:6668kb
  • [2024-07-14 19:41:22]
  • 提交

answer

#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=2e6+5,inf=1e9;const ll oo=2e18;
int n,B,cnt;pii a[N];ll ans;
il ll dis(pii x,pii y){return 1ll*(x.fi-y.fi)*(x.fi-y.fi)+1ll*(x.se-y.se)*(x.se-y.se);}
int dx[9]={0,0,1,1,1,0,-1,-1,-1};
int dy[9]={0,1,1,0,-1,-1,-1,0,1};
unordered_map<ll,int> mp;
vector<pii> e[N];
il ll id(int x,int y){return 1ll*inf*(x/B)+1ll*(y/B);}
il void add(int i){
    ll w=id(a[i].fi,a[i].se);
    if(!mp.count(w)) mp[w]=++cnt;
    e[mp[w]].push_back({a[i].fi,a[i].se});
}
int x,y,z,u,v,w;ll mi;ll p,q,r;
int main(){
    //freopen("P1429_1.in","r",stdin);
    mt19937 rnd(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&a[i].fi,&a[i].se);
    shuffle(a+1,a+1+n,rnd);
    ans=dis(a[1],a[2]),B=int(ans)+1,add(1),add(2);
    for(int i=3;i<=n;++i){
        mi=oo,u=a[i].fi/B,v=a[i].se/B;
        for(int j=0;j<9;++j){
            if(u+dx[j]<0 || v+dy[j]<0) continue;
            w=mp[1ll*(u+dx[j])*inf+(v+dy[j])];if(!w) continue;
            for(pii it:e[w]) mi=min(mi,dis(a[i],it));
        }
        if(mi>=ans){add(i);continue;}
        for(int j=1;j<=cnt;++j) e[j].clear();mp.clear();cnt=0;
        ans=mi,B=int(ans)+1;
        for(int j=1;j<=i;++j){
            p=1ll*(a[j].fi/B)*inf+(a[j].se/B),u=mp[p];if(!u) mp[p]=++cnt,u=cnt;
            e[u].push_back({a[j].fi,a[j].se});
        }
        if(clock()>1900000){double dd=sqrtl(ans);printf("%.15lf",dd);exit(0);}
    }
    double dd=sqrtl(ans);
    printf("%.15lf",dd);
    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: 4ms
memory: 6516kb

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: 4ms
memory: 6668kb

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: -15
Wrong Answer
time: 4ms
memory: 6436kb

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

result:

wrong answer 1st numbers differ - expected: '14.1421356', found: '14.3178211', error = '0.0124228'

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%