Pagini recente » Cod sursa (job #1775857) | Cod sursa (job #409594) | Cod sursa (job #1821447) | Clasament star_trek | Cod sursa (job #1076250)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#define x first
#define y second
using namespace std;
int n;
pair <int, int> Puncte[100073];
vector < pair<int ,int > > aux;
bool cmp(const pair<int, int>& a,const pair<int, int>& b)
{
return a.x < b.x;
}
bool cmp2(const pair<int, int>& a,const pair<int, int>& b)
{
return a.y<b.y;
}
double distanta(const pair<int, int>& a,const pair<int, int>& b)
{
return sqrt(1LL * (a.x-b.x) * (a.x-b.x)+1LL * (a.y-b.y)* (a.y-b.y));
}
double solve(int start, int finish)
{
if (finish-start<=3)
{
double dist= (1 << 31) - 1;
for (int i=start; i<=finish; i++)
for (int j=start; j<=finish; j++)
if(i!=j) dist=min(dist,distanta(Puncte[i],Puncte[j]));
return dist;
}
else
{
int mijloc=(start+finish)/2;
double d1=solve(start,mijloc);
double d2=solve(mijloc+1,finish);
double d=min(d1,d2);
aux.clear();
for (int i=start; i<=mijloc; i++)
if (Puncte[mijloc].x-Puncte[i].x<=d) aux.push_back(Puncte[i]);
for (int i=mijloc+1; i<=finish; i++)
if (Puncte[i].x-Puncte[mijloc].x<=d) aux.push_back(Puncte[i]);
sort(aux.begin(),aux.end(),cmp2);
int auxSize = aux.size();
for (int i=0; i < auxSize; i++)
for (int j=i + 1; j < auxSize && (j - i) < 8; j++)
d=min(d, distanta(Puncte[i],Puncte[j]));
return d;
}
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
in>>n;
for (int i=0; i<n; i++)
{
in>>Puncte[i].x>>Puncte[i].y;
}
sort(Puncte,Puncte+n,cmp);
out<<setprecision(20)<<solve(0,n-1);
return 0;
}