Pagini recente » Cod sursa (job #599303) | Istoria paginii schimbare-borland/autori | Cod sursa (job #2380903) | Cod sursa (job #1913641) | Cod sursa (job #3226258)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream cin ("cmap.in");
ofstream cout ("cmap.out");
pair <int , int> coordonate[100001] , temporar[100001];
struct Comparatie {
bool operator ()(const pair <int , int> optiune_1 , const pair <int , int> optiune_2) const
{
return optiune_1.second != optiune_2.second ? optiune_1.second < optiune_2.second : optiune_1.first < optiune_2.first;
}
};
int64_t Distanta (const pair <int , int> punct_1 , const pair <int , int> punct_2)
{
return (int64_t)(punct_1.first - punct_2.first) * (punct_1.first - punct_2.first) + (int64_t)(punct_1.second - punct_2.second) * (punct_1.second - punct_2.second);
}
int64_t Cauta (const int stanga , const int dreapta)
{
if (dreapta <= stanga)
{ return INT64_MAX; }
if (dreapta - stanga == 2)
{
if (Comparatie()(coordonate[stanga] , coordonate[dreapta]))
{ swap(coordonate[stanga] , coordonate[dreapta]); }
return Distanta(coordonate[stanga] , coordonate[dreapta]);
}
const int mijloc = (stanga + dreapta) >> 1 , pivot = coordonate[mijloc].first;
int64_t minim = min(Cauta(stanga , mijloc) , Cauta(mijloc + 1 , dreapta));
int indice_1 = stanga , indice_2 = mijloc + 1 , indice_3 = 0;
while (indice_1 <= mijloc && indice_2 <= dreapta) {
if (Comparatie()(coordonate[indice_1] , coordonate[indice_2])) { temporar[++indice_3] = coordonate[indice_1++]; }
else { temporar[++indice_3] = coordonate[indice_2++]; }
}
while (indice_1 <= mijloc)
{ temporar[++indice_3] = coordonate[indice_1++]; }
while (indice_2 <= dreapta)
{ temporar[++indice_3] = coordonate[indice_2++]; }
for (indice_2 = stanga , indice_3 = 1 ; indice_2 <= dreapta ; indice_2++ , indice_3++)
{ coordonate[indice_2] = temporar[indice_3]; }
int cantitate = 0;
for (int indice = stanga ; indice <= dreapta ; indice++) {
if ((int64_t)abs(coordonate[indice].first - pivot) * abs(coordonate[indice].first - pivot) <= minim)
{ temporar[++cantitate] = coordonate[indice]; }
}
for (int indice = 1 ; indice < cantitate ; indice++) {
for (int _indice = indice + 1 ; _indice <= min(cantitate , indice + 7) ; _indice++)
{ minim = min(minim , Distanta(temporar[indice] , temporar[_indice])); }
}
return minim;
}
int main ()
{
int numar_puncte;
cin >> numar_puncte;
for (int indice = 1 ; indice <= numar_puncte ; indice++)
{ cin >> coordonate[indice].first >> coordonate[indice].second; }
sort(coordonate + 1 , coordonate + numar_puncte + 1 , [] (const pair <int , int> optiune_1 , const pair <int , int> optiune_2) -> bool {
return optiune_1.first != optiune_2.first ? optiune_1.first < optiune_2.first : optiune_1.second < optiune_2.second;
});
cout << fixed << setprecision(6) << sqrt(Cauta(1 , numar_puncte));
cout.close(); cin.close();
return 0;
}