Pagini recente » Cod sursa (job #2724619) | Cod sursa (job #2467777) | Cod sursa (job #3194260) | Cod sursa (job #2291711) | Cod sursa (job #3226252)
#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 < 3)
{
int64_t minim = INT64_MAX;
for (int indice = stanga ; indice < dreapta ; indice++) {
for (int _indice = indice + 1 ; _indice <= dreapta ; _indice++)
{ minim = min(minim , Distanta(coordonate[indice] , coordonate[_indice])); }
}
sort(coordonate + stanga , coordonate + dreapta + 1 , Comparatie());
return minim;
}
const int mijloc = (stanga + dreapta) >> 1;
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 - coordonate[mijloc].first) * abs(coordonate[indice].first - coordonate[mijloc].first) <= 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;
}