Cod sursa(job #1194655)

Utilizator RynaquiAxinte Silviu Rynaqui Data 4 iunie 2014 15:13:47
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cmath>
#include <deque>
#define punct pair<double,double>
#define X first
#define Y second
#define N 100010
using namespace std;
punct P[N];
double cx,cy,dist(punct,punct),dei(int,int);
deque<punct> Q;
int n,i;
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf",&cx,&cy);
        P[i]=make_pair(cx,cy);
    }
    sort(P+1,P+n+1);
    printf("%.10lf",dei(1,n));
    return 0;
}
double dist(punct A,punct B)
{
    return sqrt((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y));
}
double dei(int st,int dr)
{
    double ret1,dst,ret=2000000010.0,aux,XM;
    int i,j,mi;
    if(dr-st<=2)
    {
        for(i=st;i<dr;i++)
            for(j=i+1;j<=dr;j++)
                ret=min(ret,dist(P[i],P[j]));
        for(i=st;i<=dr;i++){aux=P[i].X;P[i].X=P[i].Y;P[i].Y=aux;}
        sort(P+st,P+dr+1);
        return ret;
    }
    mi=(st+dr)/2;

    XM=(P[mi].X+P[mi+1].X)/2.0;
    ret1=ret;
    ret=dei(st,mi);
    ret=min(ret,dei(mi+1,dr));
    inplace_merge(P+st,P+mi+1,P+dr+1);
    for(i=st;i<=dr;i++)
    {
        dst=P[i].Y<XM?XM-P[i].Y:P[i].Y-XM;
        if(dst<=ret)Q.push_back(P[i]);
        if(Q.size()==7)
        {
            for(j=1;j<7;j++)
                ret1=min(ret1,dist(Q[0],Q[j]));
            Q.pop_front();
        }
        while(Q.size())
        {
            for(j=1;j<Q.size();j++)
                ret1=min(ret1,dist(Q[0],Q[j]));
            Q.pop_front();
        }
    }
    ret=min(ret,ret1);
    return ret;
}