Pagini recente » Istoria paginii utilizator/andreizaicescu | pagina legendara | Clasament dupa rating | Istoria paginii utilizator/ciobu69 | Cod sursa (job #2487966)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#define nmax 100001
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
int x,y;
};
punct pct[nmax];
int n;
bool cmp_x(punct A,punct B)
{
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
}
bool cmp_y(punct A,punct B)
{
return A.y<B.y;
}
double calc_dist(punct A,punct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double search_dist_min(punct P[],int left,int right)
{
double mn=1e9;
for(int i=left; i<right; i++)
for(int j=i+1; j<=right; j++)
{
//fout<<P[i].x<<" "<<P[i].y<<" "<<P[j].x<<" "<<P[j].y<<" "<<calc_dist(P[i],P[j])<<"\n";
if(calc_dist(P[i],P[j])<mn) mn=calc_dist(P[i],P[j]);
}
return mn;
}
double sol(punct P[],int left,int right)
{
if(right-left<=3)
return search_dist_min(P,left,right);
int mid=(right-left)/2;
double dist_left=sol(P,left,mid);
double dist_right=sol(P,mid+1,right-1);
double dist_min=min(dist_left,dist_right);
int val=P[mid].x;
punct pct_closest[nmax/2];
int ct=0;
for(int i=left; i<=right; i++)
if(abs(P[i].x-val)<dist_min)
pct_closest[++ct]=P[i];
sort(pct_closest+1,pct_closest+ct+1,cmp_y);
double dist_min_2=0;
for(int i=1; i<=ct-7; i++)
for(int j=i+1; j<=i+7; j++)
if(calc_dist(P[i],P[j])<dist_min_2) dist_min_2=calc_dist(P[i],P[j]);
//fout<<dist_min<<" "<<dist_min_2<<"\n";
return min(dist_min,dist_min);
}
int main()
{
fin>>n;
for(int i=0; i<n; i++)
{
fin>>pct[i].x>>pct[i].y;
}
sort(pct,pct+n,cmp_x);
fout<<sol(pct,0,n-1);
return 0;
}