Pagini recente » Cod sursa (job #1365247) | Cod sursa (job #2616705) | Cod sursa (job #1761261) | Cod sursa (job #885946) | Cod sursa (job #1243649)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define MAX 100010
#define INF 1LL<<62
pair<int, int> a[MAX];
long long d(pair<int, int> a, pair<int, int> b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
int rez(int st, int dr)
{
if(st==dr)
return INF;
if(st+1==dr)
{
return d(a[st], a[dr]);
}
int mid=(st+dr)>>1;
val=a[mid].second;
di=min(rez(st, mid), rez(mid+1, dr));
merge(a+st, a+mid+1, a+mid+1, a+dr+1, b);
for(i=0;i<dr-st+1;i++)
{
if(b[i].second>=val-d && b[i].first<=val+d)
{
c[++v]=b[i];
}
}
for(i=1;i<=v;i++)
{
for(j=1;j<=7 && c[i].first-c[i+j-1].first<=d;j++)
{
di=min(di, d(c[i], c[j]));
}
}
return di;
}
int main()
{
int n, i;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i].first>>a[i].second;
}
sort(a+1, a+n+1);
for(i=1;i<=n;i++)
{
swap(a[i].first, a[i].second);
}
cout<<sqrt(1.0*rez(1, n, a));
}