Mai intai trebuie sa te autentifici.
Cod sursa(job #2072691)
Utilizator | Data | 22 noiembrie 2017 08:20:39 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.79 kb |
#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;
}
};*/
double Distanta(pair<int,int> A, pair<int,int> B)
{
return sqrt((B.first - A.first) * (B.first - A.first) + (B.second - A.second) * (B.second - A.second));
}
pair<pair<pair<int,int>, pair<int,int>>, double> ClosestPoints(vector<pair<int,int>> Px, vector<pair<int,int>> Py,int left,int right)
{
if (Px.size() <= 3)
{
pair<pair<pair<int,int>, pair<int,int>>, 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;
}
int mid=(left+right)/2;
pair<int,int> midPoint = Px[mid];
//Impartim planul in 2 subplanuri
vector<pair<int,int>> Ax(Px.begin(), Px.begin() + mid);
vector<pair<int,int>> Bx(Px.begin() + mid, Px.end());
auto d1 = ClosestPoints(Ax, Py,left,mid);
auto d2 = ClosestPoints(Bx, Py,mid,right);
auto d = d1.second < d2.second ? d1 : d2; //Minimul dintre cele 2 distante;
vector<pair<int,int>> puncteDinRegiuneaLuiL;
merge(Py.begin() + left, Py.begin() + mid, Py.begin() + mid, Py.begin() + right, puncteDinRegiuneaLuiL.begin()); ///Interclasare
copy(puncteDinRegiuneaLuiL.begin(), puncteDinRegiuneaLuiL.begin() + (right - left), Py.begin() + left);
for (auto p : Py)
if (abs(p.first - midPoint.first)<d.second)
puncteDinRegiuneaLuiL.push_back(p);
for (unsigned i = 0; i < puncteDinRegiuneaLuiL.size(); i++)
{
for (unsigned j = i + 1; j < puncteDinRegiuneaLuiL.size() && (puncteDinRegiuneaLuiL[j].second - puncteDinRegiuneaLuiL[i].second) < 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<pair<int,int>> vector_puncte_sortatX;
vector<pair<int,int>> vector_puncte_sortatY;
int n;
double x, y;
FILE >> n;
while (FILE >> x >> y)
{
vector_puncte_sortatX.push_back({x,y});
vector_puncte_sortatY.push_back({x,y});
}
sort(vector_puncte_sortatX.begin(), vector_puncte_sortatX.end());
auto rezultat = ClosestPoints(vector_puncte_sortatX, vector_puncte_sortatY,0,vector_puncte_sortatX.size()-1);
FILEO << fixed << setprecision(6) << rezultat.second;
FILE.close();
FILEO.close();
return 0;
}