QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#461560 | #142. 平面最近点对 | lmeowdn | 0 | 1ms | 4184kb | C++14 | 2.0kb | 2024-07-02 20:20:11 | 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%