Cod sursa(job #869152)

Utilizator enedumitruene dumitru enedumitru Data 1 februarie 2013 00:04:15
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<cstdio> 
#include<cmath> 
#include<algorithm> 
#define inf 1000000000.0 
#define nmax 100005 
#define LL long long
using namespace std; 
struct point {int x,y;}; 
int n; 
point v[nmax],aux[nmax]; 
inline double distp(point p1, point p2) 
{	return sqrt((double)((LL)p1.x-p2.x)*(p1.x-p2.x)+((LL)p1.y-p2.y)*(p1.y-p2.y));} 
bool cmp(point p1, point p2) 
{	return p1.y<p2.y;} 
bool cmp2(point p1, point p2) 
{	return p1.x<p2.x;} 
inline double dist_min(int st, int dr) 
{   int m=(st+dr)>>1; 
    if(st>=dr) return inf; 
    if(st==dr-1) 
    {   if(v[st].y>v[dr].y) 
        {	point aux=v[st]; v[st]=v[dr]; v[dr]=aux;} 
        return distp(v[st],v[dr]); 
    } 
    int mij=v[m].x; 
    double d1=dist_min(st,m); 
    double d2=dist_min(m+1,dr); 
    double d=min(d1,d2); 
    int i1=st,i2=m+1,i=st-1; 
  
    while(i1<=m && i2<=dr) 
        if(v[i1].y<=v[i2].y) aux[++i]=v[i1++]; 
			else aux[++i]=v[i2++]; 
    for(;i1<=m;i1++) aux[++i]=v[i1]; 
    for(;i2<=dr;i2++) aux[++i]=v[i2]; 
    int nr=0; 
    for(i=st;i<=dr;i++) 
    {   v[i]=aux[i]; 
        if(abs(v[i].x-mij)<=d) aux[++nr]=v[i]; 
    } 
    double mini=inf; 
    int j; 
    for(i=1;i<=nr;i++) 
        for(j=i-1;j>=i-6 && j;j--) 
            mini=min(mini,distp(aux[i],aux[j])); 
    return min(mini,d); 
} 
int main() 
{   freopen("cmap.in","r",stdin); freopen("cmap.out","w",stdout); 
    scanf("%d",&n); 
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i].x,&v[i].y); 
    sort(v+1,v+n+1,cmp2); 
    double sol=dist_min(1,n); 
    printf("%lf\n",sol); 
    return 0; 
}