Pagini recente » Cod sursa (job #1156126) | Cod sursa (job #18457) | Cod sursa (job #755617) | Cod sursa (job #1715304) | Cod sursa (job #3226263)
#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];
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 (coordonate[stanga].second > coordonate[dreapta].second)
{ 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 (coordonate[indice_1].second <= coordonate[indice_2].first) { 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)(coordonate[indice].first - pivot) * (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;
}