Cod sursa(job #1684956)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 11 aprilie 2016 13:24:15
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 <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#define pb push_back
#define mp make_pair
#define MAXN 100001
#define INFILE "cmap.in"
#define OUTFILE "cmap.out"
#define inf 4e18
#define pct pair<long long,long long>
#define x first
#define y second
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
int n,i,a,b;
pct c[MAXN],v[MAXN];
inline bool comp(pct&a, pct& b)
{
    if(a.y==b.y)return a.x<b.x;
    return a.y<b.y;
}
inline bool compare(pct&a, pct& b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
double dist(int st, int dr)
{
    if(dr-st>3)
    {
        int m=(st+dr)/2;
        double mn=min(dist(st,m),dist(m,dr));
        int k=0,i,j;
        double C=(v[m].x+v[m-1].x)/2;
        i=m-1;
        while(C-v[i].x<=mn&&i>=st)
            c[k++]=v[i--];
        i=m;
        while(v[i].x-C<=mn&&i<dr)
            c[k++]=v[i++];
        sort(c,c+k,comp);
        for(i=0;i<k-1;i++)
            for(j=i+1;j<=i+8&&j<k;++j)
                mn=min(mn,sqrt((c[j].x-c[i].x)*(c[j].x-c[i].x)+(c[j].y-c[i].y)*(c[j].y-c[i].y)));
        return mn;
    }
    double mn=1e9;
    int i,j;
    for(i=st;i<dr-1;i++)
        for(j=i+1;j<dr;j++)
            mn=min(mn,sqrt((v[j].x-v[i].x)*(v[j].x-v[i].x)+(v[j].y-v[i].y)*(v[j].y-v[i].y)));
    return mn;
}
int main()
{
    f>>n;
    for(i=0;i<n;i++)
        f>>v[i].x>>v[i].y;
    sort(v,v+n,compare);
    g<<fixed<<setprecision(6)<<dist(0,n);
    f.close();
    g.close();
    return 0;
}