Pagini recente » Cod sursa (job #1133484) | Cod sursa (job #3268640) | Cod sursa (job #1129019) | Cod sursa (job #146741) | Cod sursa (job #3345910)
#include <bits/stdc++.h>
#define NMAX 100006
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
struct punct
{
double x,y;
} v[NMAX];
bool cmp1(punct a, punct b)
{
if(a.x!=b.x)
{
return a.x<b.x;
}
else
{
return a.y<b.y;
}
}
bool cmp2(punct a, punct b)
{
return a.y<b.y;
}
void citire()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
}
}
double dist(punct a, punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void interclasare(int st, int pmijl, int dr)
{
vector<punct> aux(dr-st+1);
int i,j,k;
i=st;
j=pmijl+1;
k=0;
while(i<=pmijl && j<=dr)
{
if(v[i].y<v[j].y)
{
aux[k++]=v[i++];
}
else
{
aux[k++]=v[j++];
}
}
while(i<=pmijl)
{
aux[k++]=v[i++];
}
while(j<=dr)
{
aux[k++]=v[j++];
}
for(int t=0; t<k; t++)
{
v[st+t]=aux[t];
}
}
double divide_et_impera(int st, int dr)
{
if(dr-st<=3)
{
double d=100000000;
d=d*10000000;
for(int i=st; i<dr; i++)
{
for(int j=i+1; j<=dr; j++)
{
d=min(d,dist(v[i],v[j]));
}
}
sort(v+st,v+dr+1,cmp2);
return d;
}
else
{
int pmijl=(st+dr)/2;
double mid=v[pmijl].x;
double d=min(divide_et_impera(st,pmijl),divide_et_impera(pmijl+1,dr));
interclasare(st,pmijl,dr);
vector<punct> banda;
for(int i=st; i<=dr; i++)
{
if(abs(v[i].x-mid)<d)
{
banda.push_back(v[i]);
}
}
for(int i=0; i<banda.size(); i++)
{
for(int j=i+1; j<banda.size() && banda[j].y-banda[i].y<d; j++)
{
d=min(d,dist(banda[i],banda[j]));
}
}
return d;
}
}
int main()
{
citire();
sort(v+1,v+1+n,cmp1);
double dmin=divide_et_impera(1,n);
fout<< fixed << setprecision(6) << dmin << "\n";
return 0;
}