Cod sursa(job #1234689)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 27 septembrie 2014 20:15:10
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>


using namespace std;
FILE *f=fopen("cmap.in","r");
FILE *g=fopen("cmap.out","w");

struct nod{
double x;
double y;
}v[100001];
int i,n;

bool cmp(nod a, nod b){
if (a.x==b.x) return a.y<b.y ;else return a.x<b.x;
}

double dist(nod a, nod b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double min1(double a, double b)
{
  if(a-b<1e-5)  return a;
  else return b;
}



double divide(int p,int u)
{
int m,i,j;
if ((u-p+1)<=3)
 return(min1(min1(dist(v[p],v[p+1]),dist(v[p+1],v[p+2])),dist(v[p],v[p+2])));
else
{
m=(p+u)/2;
double mn1=min1(divide(p,m),divide(m+1,u));
double mn2=mn1;
for(i=m;i>=p && v[m].x-v[i].x<=mn1;i--)
 for(j=1;j<=7 && i+j<=u;j++)
 mn2=min1(mn1,dist(v[i],v[i+j]));

return mn2;
}
}


int main()
{
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);

fprintf(g,"%.6lf",divide(1,n));


fclose(g);
return 0;
}