Cod sursa(job #1862965)

Utilizator vancea.catalincatalin vancea.catalin Data 30 ianuarie 2017 15:41:51
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<vector>
#include<cmath>
#define inf 5999999999
#define y second
#define x first

using namespace std;

fstream fin("cmap.in",ios::in),fout("cmap.out",ios::out);
vector<pair<int,int> > v,aux;
int n;

void citire()
{
    int i,a,b;
    fin>>n;
    for(i=0;i<n;i++)
    {
        fin>>a>>b;
        v.push_back({a,b});
    }
}
double dist(int ax,int ay,int bx,int by)
{
    long long c,d;
    c=(ax-bx);c=c*c;
    d=(ay-by);d=d*d;
    c=c+d;
    return sqrt(c);
}
double solv(int st,int dr)
{
    int m=(st+dr)/2,i,j,d;
    double minim=inf;

    if(dr-st<=3)
    {
        for(i=st;i<=dr;i++)
        {
            for(j=i+1;j<=dr;j++)
            {
                minim=min(minim,dist(v[i].x,v[i].y,v[j].x,v[j].y));
            }
        }
    }
    else
    {
        minim=min(solv(st,m),solv(m+1,dr));
        aux.clear();
        d=v[m].x;
        for(i=st;i<=dr;i++)
        {
            if(dist(v[i].x,v[i].y,d,v[i].y)<=minim)
            {
                aux.push_back(v[i]);
            }
        }
        for(i=0;i<aux.size();i++)
        {
            for(j=i+1;j<aux.size() && j<i+8;j++)
            {
                minim=min(minim,dist(aux[i].x,aux[i].y,aux[j].x,aux[j].y));
            }
        }

    }
    return minim;
}


int main()
{
    double dis;
    citire();
    sort(v.begin(),v.end());

    dis=solv(0,n-1);

    fout<<fixed<<setprecision(7)<<dis;
}