我就问问为啥70

Salamander @ 2016-10-14 12:00:11

#include<bits/stdc++.h>
using namespace std;
struct node
{
    double x,y;
}a[200001];
bool comp(node p,node q)
{
    return p.x<q.x;
}
int n;
double dis(int i,int j)
{
    return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
double find_min(int l,int r)
{
    if(l==r)return 10000000000.0;
    int mid=(l+r)/2;
    double d=min(find_min(l,mid),find_min(mid+1,r));
    double m=a[mid].x,ans=d;
    int i=mid,j=mid+1;
    while(a[i].x>=m-d&&i>l)i--;
    while(a[j].x<=m+d&&j<r)j++;
    for(;a[i].x<=m;i++)
        for(int k=j;a[k].x>=m;k--)
            if(i!=k&&abs(a[k].y-a[i].y)<=d)
            {
                double distance=dis(i,k);
                if(distance<ans)ans=distance;
            }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        double X,Y;
        scanf("%lf%lf",&X,&Y);
        a[i].x=X;
        a[i].y=Y;
    }
    sort(a+1,a+n+1,comp);
    printf("%.4lf\n",find_min(1,n));
    return 0;
}

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

看不懂

by Salamander @ 2016-10-18 19:22:59

@YJsheep 你给我滚

by YJsheep @ 2016-10-18 22:05:13

@ Excailbur 别生气呀

by liaoy14866 @ 2016-10-30 21:46:06

是否愿意尝试《算法导论》原著所说的，在元素个数<=3的时候直接暴力？

by 慕浟谭谈 @ 2017-08-16 19:26:38

附上AC代码

#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;
}