Cod sursa(job #1716165)

Utilizator refugiatBoni Daniel Stefan refugiat Data 12 iunie 2016 09:18:10
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define x first
#define y second
#define mkp make_pair
#define  ll long long
#define inf 900000000000000000
using namespace std;
ifstream si("cmap.in");
ofstream so("cmap.out");
pair<int,int> v[100005],aux[100005];
bool cmp(pair<int,int> a,pair<int,int> b)
{
    if(a.y<b.y)
        return true;
    if(a.y==b.y)
        if(a.x<b.x)
            return true;
    return false;

}
ll dist(pair<int,int> a,pair<int,int> b)
{
    return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}

ll rezolva(int st,int dr)
{
    if(st>=dr)
        return inf;
    if(st==dr-1)
    {
        if(cmp(v[dr],v[st]))
        {
            swap(v[st],v[dr]);
        }
        return dist(v[st],v[dr]);
    }
    int mid=(st+dr)/2,midx=v[mid].x;
    ll sol=min(rezolva(st,mid),rezolva(mid+1,dr));
    merge(v+st,v+mid+1,v+mid+1,v+dr+1,aux+1,cmp);
    int i,j,nr=0;
    for(i=1;i<=dr-st+1;i++)
        v[st+i-1]=aux[i];
    for(i=1;i<=dr-st+1;i++)
        if(1LL*abs(aux[i].x-midx)*abs(aux[i].x-midx)<=sol)
        aux[++nr]=aux[i];
    for(i=1;i<=nr;i++)
        for(j=i+1;j<=nr&&1LL*(aux[j].y-aux[i].y)*(aux[j].y-aux[i].y)<=sol;j++)
            sol=min(sol,dist(aux[i],aux[j]));
    return sol;
}
int main()
{
    int n;
    si>>n;
    int i,a,b;
    for(i=1;i<=n;i++)
    {
        si>>a>>b;
        v[i]=mkp(a,b);
    }
    sort(v+1,v+1+n);
    //for(i=1;i<=n;++i)
      //  cout<<v[i].x<<' '<<v[i].y<<'\n';
    so<<sqrt(rezolva(1,n));
    return 0;
}