顶一下
by Salamander @ 2016-10-15 17:09:46
大神:我看了,没什么事,那我走了
by YJsheep @ 2016-10-17 22:07:45
可能数组爆了吧
by M_seа @ 2016-10-17 22:19:27
看不懂
by M_seа @ 2016-10-17 22:20:41
@[YJsheep](/space/show?uid=20133) 你给我滚
by Salamander @ 2016-10-18 19:22:59
@ Excailbur 别生气呀
by YJsheep @ 2016-10-18 22:05:13
是否愿意尝试《算法导论》原著所说的,在元素个数<=3的时候直接暴力?
by liaoy14866 @ 2016-10-30 21:46:06
附上AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2000010;
typedef double db;
typedef long long ll;
struct poi{
ll x,y;
inline friend ll dis(const poi a,const poi b){
return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);
}
}a[N],b[N];
inline bool cmpx(const poi&a,const poi&b){
return a.x<b.x;
}
inline bool cmpy(const poi&a,const poi&b){
return a.y<b.y;
}
int n,i;
inline void up(ll&x,const ll&y){
if(x>y)x=y;
}
inline ll min(const ll&x,const ll&y){
return x>y?y:x;
}
inline ll sqr(ll x){
return x*x;
}
ll solve(int l,int r){
if(l>=r-2)return l==r-1?dis(a[l],a[r]):min(min(dis(a[l],a[l+1]),dis(a[l+1],a[l+2])),dis(a[l+2],a[l]));
int m=(l+r)>>1,u,i,s,t,v,j;
ll dd=min(solve(l,m),solve(m+1,r)),x=(a[m].x+a[m+1].x)/2,d=dd;
for(s=m;s>=l && sqr(a[s].x-x)<=dd;--s)b[s]=a[s];
for(t=m+1;t<=r && sqr(a[t].x-x)<=dd;++t)b[t]=a[t];
++s,--t;
std::sort(b+s,b+m+1,cmpy);
std::sort(b+m+1,b+t+1,cmpy);
for(i=s,u=v=m+1;i<=m;++i){
while(dd<sqr(b[i].y-b[u].y) && b[u].y<=b[i].y)++u;
while(v<=t && (b[v].y<=b[i].y || (b[v].y-b[i].y)<=dd))++v;
--v;
for(j=u;j<=v;++j)up(d,dis(b[i],b[j]));
}
return d;
}
int main(){
//freopen("1.txt","r",stdin);
//freopen("2.txt","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%lld%lld",&a[i].x,&a[i].y);
if(n==1){
puts("0");
return 0;
}
std::sort(a+1,a+n+1,cmpx);
printf("%.4f\n",sqrt(solve(1,n)));
return 0;
}
```
by 慕浟谭谈 @ 2017-08-16 19:26:38