Pagini recente » Cod sursa (job #2850766) | Cod sursa (job #2968746) | Cod sursa (job #1975083) | Cod sursa (job #1453161) | Cod sursa (job #1765454)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define oo 1000000005
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int N;
double sol;
pair <int,int>puncte[100005];
void read()
{
fin>>N;
for(int i=1;i<=N;i++)
{
fin>>puncte[i].first>>puncte[i].second;
}
sort(puncte+1,puncte+1+N);
}
double dist(pair <int,int>A,pair<int, int > B)
{
return sqrt(1LL*(A.first-B.first)*(A.first-B.first)+1LL*(A.second-B.second)*(A.second-B.second));
}
bool comp(pair<int,int>A,pair<int,int>B)
{
return A.second>B.second;
}
double DEI(int left,int right)
{
double S=oo,S1=oo,S2=oo;
if(right-left > 3)
{
int mid=(left+right)/2;
S1=DEI(left,mid);
S2=DEI(mid+1,right);
S=min(S1,S2);
}
else
{
for(int i=left;i<right;i++)
{
for( int j=i+1;j<=right;j++)
{
S=min(S,dist(puncte[i],puncte[j]));
}
}
return S;
}
int mid=(left+right)/2;
int middle = (puncte[mid].first+puncte[mid+1].first)/2;
pair <int,int> Y[1000];
int k=0;
for(int i=left;i<=right;i++)
{
if(abs(puncte[i].first-middle)<=S)
{
Y[++k]=puncte[i];
}
}
sort(Y+1,Y+k+1,comp);
for(int i=1;i<=k;i++)
{
for(int j=i+1;j<=i+8;j++)
{
S=min(S,dist(puncte[i],puncte[j]));
}
}
return S;
}
void solve()
{
sol=DEI(1,N);
}
void print()
{
fout<<fixed<<setprecision(6)<<sol<<"\n";
}
int main()
{
read();
solve();
print();
}