Pagini recente » Cod sursa (job #2752383) | Cod sursa (job #955531) | Cod sursa (job #2092083) | Cod sursa (job #280277) | Cod sursa (job #1076227)
#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];
bool cmp(const pair<int, int>& a,const pair<int, int>& b)
{
if (a.x>b.x) return false;
else if (a.x<b.x) return true;
else if (a.x==b.x) return a.y<b.y;
}
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((a.x-b.x) * 1.0 *(a.x-b.x)+(a.y-b.y)* 1.0 *(a.y-b.y));
}
double solve(int start, int finish)
{
if (finish-start<=3)
{
double dist= 1.0 * (1 << 20);
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);
vector<pair<int, int> > aux;
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);
for (int i=0;i<aux.size();i++)
for (int j=1;j<8 && i+j<aux.size();j++)
d=min(d, distanta(Puncte[i],Puncte[i+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;
}