Pagini recente » Cod sursa (job #3191270) | Cod sursa (job #1932375) | Cod sursa (job #1787421) | Cod sursa (job #1575443) | Cod sursa (job #2482742)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Point
{
long long x,y;
};
void read(int &n, vector <Point> &v)
{
fin>>n;
v.resize(n);
for(int i=0;i<n;i++)
fin>>v[i].x>>v[i].y;
}
bool cmp(Point a, Point b)
{
return ((a.x<b.x) || (a.x==b.x && a.y<b.y));
}
long long distance(Point a, Point b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
void merge_function(int st,int m,int dr,vector <Point> &v)
{
int i=st,j=m+1;
vector <Point> aux;
while(i<=m && j<=dr)
{
if(v[i].y<v[j].y)
aux.push_back(v[i++]);
else aux.push_back(v[j++]);
}
while(i<=m)
aux.push_back(v[i++]);
while(j<=dr)
aux.push_back(v[j++]);
int index=st;
for( Point a : aux)
{
v[index]=a;
index++;
}
}
long long divide(int st,int dr, vector <Point> v)
{
if(dr-st==1)
{
int minim=distance(v[st],v[dr]);
if(v[st].y>v[dr].y) //sortam dupa ordonata
swap(v[st],v[dr]);
return minim;
}
else if(dr-st==2)
{
int minim=min(distance(v[st],v[st+1]),min(distance(v[st],v[dr]),distance(v[dr],v[st+1])));
if(v[st].y>v[st+1].y) //sortam cele 3 valori din v dupa ordonata
swap(v[st],v[st+1]);
if(v[st].y>v[dr].y)
swap(v[st],v[dr]);
if(v[st+1].y>v[dr].y)
swap(v[st+1],v[dr]);
return minim;
}
else
{
int m=(st+dr)/2;
long long mst=divide(st,m,v);
long long mdr=divide(m+1,dr,v);
long long minim=min(mst,mdr);
merge_function(st,m,dr,v); //se sorteaza partea stanga si dreapta dupa ordonata
vector <Point> aux;
for(int i=st ; i<=dr ; i++)
if(abs(v[i].x-v[m].x)<=minim) //punem intr-un vector punctele care se afla la distanta minim fata de dreapta imaginara verticala ce imparte partea stanga de cea dreapta
aux.push_back(v[i]);
int siz=aux.size();
for(int i=0;i<siz;i++) //vedem daca exista o distanta intre doua pct mai mica decat minim cu un pct din dreapta si unul din stanga
for(int j=i+1; j<siz-1 && j<=i+7; j++)
if(distance(v[i],v[j])<minim)
minim=distance(v[i],v[j]);
return minim;
}
}
int main()
{
int n;
vector <Point> v;
read(n,v);
sort(v.begin(),v.end(),cmp);
fout<<fixed<<setprecision(6)<<(double)sqrt( divide(0,n-1,v) );
return 0;
}