Pagini recente » Cod sursa (job #2536382) | Cod sursa (job #2352838) | Cod sursa (job #2043063) | Cod sursa (job #1385761) | Cod sursa (job #1075305)
#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;
double dist(punct a, punct b)
{
double ax=a.x,bx=b.x,ay=a.y,by=b.y;
return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
double ddcmap(int pst, int pdr)
{
if (pdr-pst<=2)
if (pdr-pst == 1)
return dist(p[pdr],p[pst]);
else
{
double d1 = dist(p[pst],p[pst+1]);
double d2 = dist(p[pst],p[pdr]);
double d3 = dist(p[pdr],p[pst+1]);
return min(min(d1,d2),d3);
}
else
{
int m= (pst+pdr)/2,i,j;
double s1 = ddcmap(pst, m);
double s2 = ddcmap(m+1, pdr);
double smin = min(s1,s2);
//vector <punct> v;
j=0;
for (i=m+1;i<n;i++)
{
if (p[i].x > p[m].x+smin)
break;
pp[j++]=p[i];
}
int p2 = i-1;
for (i=m;i>=0;i--)
{
if (p[i].x < p[m].x - smin)
break;
//v.push_back(p[i]);
pp[j++]=p[i];
}
int 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+3;ii++)
{
double d1 = dist(p[i],p[ii]);
if(d1<smin)
smin=d1;
}
//for(int i=p1; i <=m ; i++)
//for(int j=m+1; j<=p2; j++)
//{ double 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 << " ";
double rez = ddcmap(0,n-1);
g.precision(18);
g<<rez << endl;
//cout.precision(18);
//cout << rez << endl;
return 0;
}