Cod sursa(job #590644)

Utilizator drywaterLazar Vlad drywater Data 18 mai 2011 23:14:28
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <math.h>
#include <algorithm>
#include <iomanip>
#define INF 4e18
using namespace std;
int n,i,j,vs,ly2;
struct punct{long long x; long long y;};
punct x[100005],y[100005],v[100005],y2[100005];
int cmp(punct a,punct b)
{
    if (a.x!=b.x)
    return (a.x<b.x);
    return (a.y<b.y);
}
inline void swap(punct &a,punct &b)
{
    punct aux=a;
    a=b;
    b=aux;
}
long long dist(punct x,punct y)
{
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
inline long long min(long long a,long long b)
{
    if (a>b) return b;
    return a;
}
long long apel(int st,int dr)
{
    if (st>=dr-1) return INF;
    if (dr-st==2)
    {
        if (y[st].x>y[st+1].x || (y[st].x==y[st+1].x && y[st].y>y[st+1].y))
            swap(y[st],y[st+1]);
        return dist(x[st],x[st+1]);
    }
    int m=(st+dr)/2;
    long long best=min(apel(st,m),apel(m,dr));
    i=st;
    j=m;
    ly2=st;
    while (ly2<dr)
    {
        if (i>=m){y2[ly2]=y[j]; j++; ly2++;continue;}
        if (j>=dr) {y2[ly2]=y[i]; i++; ly2++;continue;}
        if (y[i].x>y[j].x || (y[i].x==y[j].x && y[i].y>y[j].y))
        {y2[ly2]=y[j]; j++; ly2++;continue;}
        y2[ly2]=y[i]; i++; ly2++;continue;
    }
    vs=0;
    for (i=st;i<dr;i++)
    {
        y[i]=y2[i];
        if (abs(y[i].y-x[m].x)<=best)
            v[++vs]=y[i];
    }
    for (i=1;i<=vs;i++)
    {
        for (j=i+1;j<=vs && j-i<=7;j++)
            best=min(best,dist(v[i],v[j]));
    }
    return best;
}
int main(void)
{
    ifstream f("cmap.in");
    ofstream o("cmap.out");
    f>>n;
    for (i=1;i<=n;i++)
        f>>x[i].x>>x[i].y;
    sort(x+1,x+n+1,cmp);
    for (i=1;i<=n;i++)
    {
        y[i].x=x[i].y;
        y[i].y=x[i].x;
    }
    o<<fixed<<setprecision(6)<<sqrt(apel(1,n+1));
    return 0;
}