Cod sursa(job #1838176)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 31 decembrie 2016 12:11:17
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100001
using namespace std;
FILE *f=fopen("cmap.in","r");
FILE *g=fopen("cmap.out","w");
typedef pair<long long,long long> point;
vector <point> V(NMAX);
vector<point> X,Y;
int N;
long long dist(point a,point b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
long long getmin(int st,int dr)///st...dr-1
{
    if(st>=dr-1)
        return (1LL<<62);
    if(st==dr-2)
    {
        if(Y[dr-1]<Y[st])
            swap(Y[st],Y[dr-1]);
        return dist(Y[st],Y[dr-1]);
    }
    int mid=(st+dr)/2;
    long long minim=min(getmin(st,mid),getmin(mid,dr));
    merge(Y.begin()+st,Y.begin()+mid,Y.begin()+mid,Y.begin()+dr,V.begin());
    copy(V.begin(),V.begin()+(dr-st),Y.begin()+st);
    int ind=0;
    for(int i=st;i<dr;i++)
        if(abs(Y[i].second-X[i].first)<=minim)
            V[ind++]=Y[i];
    for(int i=0;i<ind;i++)
        for(int j=i+1;j<ind&&j-i<=7;j++)
            minim=min(minim,dist(V[j],V[i]));
    return minim;
}
int main()
{
    fscanf(f,"%d",&N);
    X.resize(N);
    Y.resize(N);
    for(int i=0;i<N;i++)
        fscanf(f,"%d%d",&X[i].first,&X[i].second);
    for(int i=0;i<N;i++)
        Y[i]=make_pair(X[i].second,X[i].first);
    fprintf(g,"%.6f",sqrt(double(getmin(0,N))));
    fclose(f);
    fclose(g);
    return 0;
}