Pagini recente » Cod sursa (job #2968127) | Cod sursa (job #1010851) | Cod sursa (job #1607671) | Cod sursa (job #1823335) | Cod sursa (job #1080074)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f ("cmap.in");
ofstream g ("cmap.out");
struct punct {int x,y;} ;
punct p[100001],pp[100001];
int compx(punct a, punct b)
{
if (a.x < b.x)
return 1;
else
return 0;
}
int compy(punct a, punct b)
{
if (a.y < b.y)
return 1;
else
return 0;
}
int n, i, k=1;
long dist(punct a, punct b)
{
long ax=a.x,bx=b.x,ay=a.y,by=b.y;
return ((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
long ddcmap(long pst, long pdr)
{
if (pdr-pst<=2)
if (pdr-pst == 1)
return dist(p[pdr],p[pst]);
else
{
long d1 = dist(p[pst],p[pst+1]);
long d2 = dist(p[pst],p[pdr]);
long d3 = dist(p[pdr],p[pst+1]);
return min(min(d1,d2),d3);
}
else
{
int m= (pst+pdr)/2,i,j;
long s1 = ddcmap(pst, m);
long s2 = ddcmap(m+1, pdr);
long smin = (min(s1,s2));
//vector <punct> v;
j=0;
for (i=m+1;i<n;i++)
{
if ((p[i].x - p[m].x)*(p[i].x - p[m].x) > smin)
break;
pp[j++]=p[i];
}
int pd = i;
//long p2 = i-1;
for (i=m;i>=0;i--)
{
if ((p[m].x - p[i].x)*(p[m].x - p[i].x) > smin)
break;
//v.push_back(p[i]);
pp[j++]=p[i];
}
int ps = i;
//long p1 = i+1;
//k++;
//cout << p[m].x<<' '<<p[p1].x<<' '<<p[p2].x<<' ';
//cout << smin << ' '<< m-p1+1<<' '<<p2-m+1<<" ";
//if (k%200==0)
// system("pause");
sort(pp,pp+j,compy);
for (i=0;i< j;i++)
for (int ii=i+1;ii<j && ii<=i+7;ii++)
{
long d1 = dist(p[i],p[ii]);
if(d1<smin)
smin=d1;
}
//for(long i=p1; i <=m ; i++)
//for(long j=m+1; j<=p2; j++)
//{ long d1 = dist(p[i],p[j]);
// if(d1<smin) smin=d1; }
return smin;
}
}
int main()
{
f >> n;
for(i=0; i<n; i++)
f >> p[i].x >> p[i].y;
sort(p,p+n,compx);
//for (i=0;i<n;i++)
//cout << p[i].x << ' ' << p[i].y << " ";
long rez = ddcmap(0,n-1);
g.precision(18);
g<<sqrt(rez) << endl;
//cout.precision(18);
//cout << sqrt(rez) << endl;
return 0;
}