Cod sursa(job #1617457)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 27 februarie 2016 14:02:50
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100000,INF=1000000000;
class Point{
    public:
        int x,y;
        bool operator<(const Point&p)const{
            if(x==p.x)
                return y<p.y;
            return x<p.x;
        }
};
Point p[N+1];
int n;
long long dist(Point p1,Point p2){
    return (p1.x-p2.x)*1LL*(p1.x-p2.x)+(p1.y-p2.y)*1LL*(p1.y-p2.y);
}
long long divide(int l,int r){
    if(r-l<=2)
        return min(min(dist(p[l],p[l+1]),dist(p[l],p[l+2])),dist(p[l+1],p[l+2]));
    else{
        int m=(l+r)/2;
        int i,j;
        long long d2=min(divide(l,m),divide(m,r));
        for(i=m;i>=l&&p[m].x-p[i].x<=d2;i--)
            for(j=m+1;j<=r&&p[j].x-p[m].x<=d2;j++)
                d2=min(d2,dist(p[i],p[i+j]));
        return d2;
    }
}
int main(){
    int i;
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    sort(p+1,p+n+1);
    printf("%lf",sqrt(divide(1,n)));
    return 0;
}