Pagini recente » Rating Scarlett Gonzales (acinstallation439) | Diferente pentru preoni-2007/runda-4/solutii intre reviziile 24 si 34 | Istoria paginii utilizator/mada_fucku | Cod sursa (job #2014371) | Cod sursa (job #2072676)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;
struct Punct2D
{
double x;
double y;
Punct2D(double xx, double yy)
{
x = xx;
y = yy;
}
};
bool SorteazaDupaX(const Punct2D& A, const Punct2D& B)
{
if (A.x > B.x)
return false;
if (A.x == B.x)
{
if (A.y > B.y)
return false;
else
return true;
}
return true;
}
bool SorteazaDupaY(const Punct2D& A, const Punct2D& B)
{
if (A.y > B.y)
return false;
if (A.y == B.y)
{
if (A.x > B.x)
return false;
else
return true;
}
return true;
}
double Distanta(Punct2D A, Punct2D B)
{
return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y));
}
vector<Punct2D> Merge(vector<Punct2D> A, vector<Punct2D> B)
{
unsigned i = 0;
unsigned j = 0;
vector<Punct2D> vector_sortat;
while (i<A.size() && j<B.size())
{
if (A[i].y <= B[j].y)
{
vector_sortat.push_back(A[i]);
i++;
}
else
if (A[i].y > B[j].y)
{
vector_sortat.push_back(B[j]);
j++;
}
}
if (i != A.size())
for (unsigned aux = i; aux<A.size(); aux++)
vector_sortat.push_back(A[aux]);
else
if (j != B.size())
for (unsigned aux = j; aux<B.size(); aux++)
vector_sortat.push_back(B[aux]);
return vector_sortat;
}
pair<pair<Punct2D, Punct2D>, double> ClosestPoints(vector<Punct2D> Px, vector<Punct2D> Py)
{
if (Px.size() <= 3)
{
pair<pair<Punct2D, Punct2D>, double> min = make_pair(make_pair(Px[0], Px[0]), 2147483647);
if (Px.size() == 1)
return min;
for (unsigned i = 0; i<Px.size(); i++)
for (unsigned j = i + 1; j<Px.size(); j++)
if (Distanta(Px[i], Px[j]) < min.second)
min = make_pair(make_pair(Px[i], Px[j]), Distanta(Px[i], Px[j]));
return min;
}
Punct2D midPoint = Px[Px.size() / 2];
//Impartim planul in 2 subplanuri
vector<Punct2D> Ax(Px.begin(), Px.begin() + Px.size() / 2);
vector<Punct2D> Bx(Px.begin() + Px.size() / 2, Px.end());
vector<Punct2D> Ay;
vector<Punct2D> By;
for (auto p : Py)
{
if (p.x <= midPoint.x)
Ay.push_back(p);
else
By.push_back(p);
}
auto d1 = ClosestPoints(Ax, Ay);
auto d2 = ClosestPoints(Bx, By);
auto d = d1.second < d2.second ? d1 : d2; //Minimul dintre cele 2 distante;
Py=merge(Ay,By);
vector<Punct2D> puncteDinRegiuneaLuiL;
for (auto p : Py)
if (abs(p.x - midPoint.x)<d.second)
puncteDinRegiuneaLuiL.push_back(p);
for (unsigned i = 0; i < puncteDinRegiuneaLuiL.size(); i++)
{
for (unsigned j = i + 1; j < puncteDinRegiuneaLuiL.size() && (puncteDinRegiuneaLuiL[j].y - puncteDinRegiuneaLuiL[i].y) < d.second; j++)
d = Distanta(puncteDinRegiuneaLuiL[i], puncteDinRegiuneaLuiL[j]) < d.second ? make_pair(make_pair(puncteDinRegiuneaLuiL[i], puncteDinRegiuneaLuiL[j]), Distanta(puncteDinRegiuneaLuiL[i], puncteDinRegiuneaLuiL[j])) : d;
}
return d;
}
int main()
{
ifstream FILE("cmap.in");
ofstream FILEO("cmap.out");
vector<Punct2D> vector_puncte_sortatX;
vector<Punct2D> vector_puncte_sortatY;
int n;
double x, y;
FILE >> n;
while (FILE >> x >> y)
{
vector_puncte_sortatX.push_back(Punct2D(x, y));
vector_puncte_sortatY.push_back(Punct2D(x, y));
}
sort(vector_puncte_sortatX.begin(), vector_puncte_sortatX.end(), SorteazaDupaX);
auto rezultat = ClosestPoints(vector_puncte_sortatX, vector_puncte_sortatY);
FILEO << fixed << setprecision(6) << rezultat.second;
FILE.close();
FILEO.close();
return 0;
}