Pagini recente » Cod sursa (job #194439) | Cod sursa (job #2502904) | Cod sursa (job #1817998) | Cod sursa (job #1262336) | Cod sursa (job #2485381)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const long long infinit = 4e18;
struct triplet
{
pair<long long,long long> p1,p2;
long long distanta;
};
void interclasare(int p, int m, int q, vector< pair<long long,long long> > & v)
{
vector< pair<long long,long long> > aux;
int i = p, j = m;
while(i<m && j<q)
if(v[i].first <= v[j].first)
aux.push_back(v[i++]);
else
aux.push_back(v[j++]);
while(i<m)
aux.push_back(v[i++]);
while(j<q)
aux.push_back(v[j++]);
for(int i=0; i < (int)aux.size(); i++)
v[p+i] = aux[i];
}
long long dist(pair<long long,long long> a, pair<long long,long long> b)
{
return ((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
triplet DI(int st, int dr, vector< pair<long long,long long> > & v, vector< pair<long long,long long> > & u)
{
if(dr-st < 2)
{
triplet inf;
inf.distanta = infinit;
inf.p1 = {infinit,infinit};
inf.p2 = {infinit,infinit};
return inf;//daca multimea are cel mult un element, distanta va fi infinit, semnificand ca nu exista puncte intre care sa o calculez
}
if(dr-st == 2)
{
if(u[st].first > u[dr-1].first)// sorteaza u dupa ordonata
swap(u[st],u[dr-1]);
triplet d;
d.distanta = dist(v[st],v[dr-1]);
d.p1 = v[st];
d.p2 = v[dr-1];
return d;//multimea are exact doua puncte, deci distanta minima este exact distanta dintre ele
}
int m=(st+dr)/2;
triplet D1 = DI(st, m, v, u);//calculez distanta minima de pe partea stanga
triplet D2 = DI(m, dr, v, u);//calculez distanta minima de pe partea dreapta
triplet D_min;//aflu minimul dintre cele doua distante de mai sus
if(D1.distanta < D2.distanta)
D_min = D1;
else
D_min = D2;
interclasare(st, m, dr, u);//interclaseaza in functie de ordonata cele doua multimmi de puncte
vector< pair<long long,long long> > proxim;//vector care va contine punctele din u cu ordonata la distanta <= D_min fata de dreapta reprezentata de abscisa elementului de pe pozitia m din v
for(int i=st ;i < dr; i++)
if(abs(u[i].second-v[m].first) <= D_min.distanta)//adaug in proxim toate punctele care au distanta dintre abscisa si abscisa lui v[m] <= D_min
proxim.push_back(u[i]);
for(int i=0; i < (int)proxim.size()-1; i++)
for(int j=i+1; j < (int)proxim.size() && j-i<8 ; j++)
if(D_min.distanta > dist(proxim[i],proxim[j]))
{
D_min.distanta = dist(proxim[i],proxim[j]);
D_min.p1.first = proxim[i].second;
D_min.p1.second = proxim[i].first;
D_min.p2.first = proxim[j].second;
D_min.p2.second = proxim[j].first;
}
return D_min;
}
int main()
{
int n;
fin>>n;
vector< pair<long long,long long> > v(n);
for(int i=0; i<n; i++)
fin>>v[i].first>>v[i].second;
sort(v.begin(), v.end());
vector< pair<long long,long long> > u(n);
for(int i=0; i<n; i++)
{
u[i].first = v[i].second;
u[i].second = v[i].first;
}
triplet mini = DI(0, n, v, u);
fout<<fixed<<setprecision(6)<<sqrt(mini.distanta);
return 0;
}