Cod sursa(job #2061005)

Utilizator mihailrazMihail Turcan mihailraz Data 8 noiembrie 2017 20:53:52
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fi("cmap.in");
ofstream fo("cmap.out");
int n;
struct PUNCT
{
    int x, y;
} P[100001],Y[100001],B[100001],Z[100001];

inline double distanta(PUNCT a, PUNCT b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int cmp(PUNCT a, PUNCT b)
{
    return (a.x<b.x);
}

int cmpy(PUNCT a, PUNCT b)
{
    return (a.y<b.y);
}

double divImp(int st, int dr)
{
    if(dr-st==1)
    {
        if(B[st].y>B[dr].y)
        {
            swap(B[st].x,B[dr].x);
            swap(B[st].y,B[dr].y);
        }
        return distanta(P[st],P[dr]);
    }
    if(dr-st==2)
    {
        sort(B+st,B+dr+1,cmpy);
        return min(distanta(P[st],P[st+1]),min(distanta(P[st+1],P[dr]),distanta(P[st],P[dr])));
    }
    int mij=(st+dr)/2,i,j,k;
    double d=min(divImp(st,mij),divImp(mij+1,dr));
    for(i=st, j=mij+1, k=st; i<=mij && j<=dr; )
        if(B[i].y<B[j].y)
            Y[k++]=B[i++];
        else
            Y[k++]=B[j++];
    while(i<=mij)
        Y[k++]=B[i++];
    while(j<=dr)
        Y[k++]=B[j++];
    for(int ind=st; ind<=dr; ind++)
        B[ind]=Y[ind];
    int nr=0;
    for(int ind=st,i=1; ind<=dr; ind++)
        if(abs(P[mij].x-B[ind].x)<=d)
        {
            Z[i].x=B[ind].x;
            Z[i++].y=B[ind].y;
            nr++;
        }
    for(i=1; i<=nr-7; i++)
        for(int j=i; j<=nr && j<=i+7; j++)
            d=min(distanta(Z[i],Z[j]),d);
    return d;
}


int main()
{
    fi>>n;
    for(int i=1; i<=n; i++)
        fi>>P[i].x>>P[i].y;
    sort(P+1,P+n+1,cmp);
    for(int i=1; i<=n; i++)
    {
        B[i].x=P[i].x;
        B[i].y=P[i].y;
    }
    fo<<fixed<<setprecision(6)<<divImp(1,n);
    fi.close();
    fo.close();
    return 0;
}