QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#461560#142. 平面最近点对lmeowdn0 1ms4184kbC++142.0kb2024-07-02 20:20:112024-07-02 20:20:11

Judging History

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

  • [2024-07-02 20:20:11]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4184kb
  • [2024-07-02 20:20:11]
  • 提交

answer

//Shirasu Azusa 2024.7
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;  
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=2e6+5; const double inf=1e18;
int n; double ans=inf;
struct node {double x,y;} a[N];
bool cmpx(const node &x,const node &y) {return x.x<y.x;}
bool cmpy(const node &x,const node &y) {return x.y<y.y;}
double dis(const node a,const node b) {
  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void work(int l,int r) {
  if(l==r) return; int mid=l+r>>1; double w=a[mid].x;
  work(l,mid), work(mid+1,r);
  static node p[N],q[N]; int x=0,y=0;
  rep(i,l,mid) if(w-a[i].x<ans) p[++x]=a[i];
  rep(i,mid+1,r) if(a[i].x-w<ans) q[++y]=a[i];
  for(int i=1,s=1,t=0;i<=x;i++) {
    while(s<=y&&p[i].y-q[s].y>ans) s++;
    while(t<y&&q[t+1].y-p[i].y<ans) t++;
    rep(j,s,t) chmin(ans,dis(p[i],q[j]));
  }
  inplace_merge(a+l,a+mid+1,a+r,cmpy);
}

signed main() {
  n=read();
  rep(i,1,n) a[i].x=read(), a[i].y=read();
  sort(a+1,a+n+1,cmpx); work(1,n);
  printf("%.8lf\n",ans);
  return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 15
Accepted
time: 1ms
memory: 4184kb

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

result:

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

Test #2:

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

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:

13.60147051

result:

wrong answer 1st numbers differ - expected: '8.6023253', found: '13.6014705', error = '0.5811388'

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%