Pagini recente » Cod sursa (job #1349340) | Cod sursa (job #1821892) | Cod sursa (job #2484121) | Cod sursa (job #1486794) | Cod sursa (job #3348317)
#include <bits/stdc++.h>
#define NMAX 100000
#define x first
#define y second
#define E (1e-6)
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
pair<int, int> puncte[NMAX+1];
long double dist(pair<int, int> a, pair<int, int> b) ///distanta intre 2 puncte
{
return sqrt(((long double)a.x-b.x)*(a.x-b.x) + ((long double)a.y-b.y)*(a.y-b.y));
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
long double solve(int st, int dr) ///divide et impera
{
if(dr-st<=3)
{
long double minim=dist(puncte[st], puncte[dr]);
if(dr-st==3)
{
minim=min(minim, dist(puncte[st], puncte[st+1]));
minim=min(minim, dist(puncte[st+1], puncte[dr]));
}
return minim;
}
int mij=st+(dr-st)/2;
int d=puncte[mij].y; ///coordonata dreptei care imparte punctele in doua multimi
long double dist_st=solve(st, mij);
long double dist_dr=solve(mij+1, dr);
long double dist_min=min(solve(st, mij), solve(mij+1, dr));
vector<pair<int, int>> candidati; ///punctele situate la o distanta mai mica ca dist_min fata de dreapta d
for(int i=st; i<=dr; i++)
{
if(abs(d-puncte[i].y)<dist_min)
candidati.push_back(puncte[i]);
}
sort(candidati.begin(), candidati.end(), cmp);
for(int i=0; i<candidati.size(); i++)
{
for(int j=i+1; j<candidati.size() && j<i+8; j++)
{
dist_min=min(dist_min, dist(candidati[i], candidati[j]));
}
}
candidati.clear();
return dist_min;
}
int main()
{
int n;
in >> n;
for(int i=1; i<=n; i++)
{
in >> puncte[i].x >> puncte[i].y;
}
sort(puncte+1, puncte+n+1);
out << fixed << setprecision(6) << solve(1, n);
return 0;
}