Pagini recente » Cod sursa (job #38018) | Cod sursa (job #1636924) | Cod sursa (job #2142757) | Cod sursa (job #111061) | Cod sursa (job #2072409)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct
{
int x = 0;
int y = 0;
};
double distEuclid(punct a, punct b)
{
double x = a.x - b.x;
double y = a.y - b.y;
double dist;
dist = pow(x, 2) + pow(y, 2);
dist = sqrt(dist);
return dist;
}
bool cmpDupaX(const punct& a, const punct& b)
{
return a.x < b.x;
}
bool cmpDupaY(const punct& a, const punct& b)
{
return a.y < b.y;
}
double distMinPunctePlanRec(vector <punct> & puncte, int st, int dr, vector<punct> &puncteY)
{
if (dr - st == 1)
{
return 2147483647; //int_max
}
if (dr - st == 2)
{
if (puncteY[st].y > puncteY[st + 1].y)
swap(puncteY[st], puncteY[st + 1]);
return distEuclid(puncte[0], puncte[1]);
}
int m = (st + dr) / 2;
double distStanga = distMinPunctePlanRec(puncte, st, m, puncteY);
double distDreapta = distMinPunctePlanRec(puncte, m, dr, puncteY);
double distMinStDr = min(distStanga, distDreapta);
vector <punct> puncteAux(dr - st);
merge(puncteY.begin() + st, puncteY.begin() + m, puncteY.begin() + m, puncteY.begin() + dr, puncteAux.begin(), cmpDupaY);
copy(puncteAux.begin(), puncteAux.begin() + (dr - st), puncteY.begin() + st);
/// crearea benzii
vector <punct> banda;
for (int i = st; i < dr; ++i)
{
if (abs(puncteY[i].x - puncte[m].x) <= distMinStDr)
banda.push_back(puncteY[i]);
}
/// verificarea benzii
double distMinOverall = distMinStDr;
for (int i = 0; i<banda.size(); ++i)
for (int j = i + 1; j < banda.size() && banda[j].y - banda[i].y <= distMinStDr; ++j)
{
double distCur = distEuclid(banda[i], banda[j]);
if (distCur < distMinOverall)
distMinOverall = distCur;
}
return distMinOverall;
}
void distMinPunctePlan()
{
int n;
cin >> n;
vector <punct> puncte(n);
for (int i = 0; i < n; ++i)
{
cin >> puncte[i].x;
cin >> puncte[i].y;
}
sort(puncte.begin(), puncte.end(), cmpDupaX); /// sortam punctele dupa x
vector <punct> puncteY = puncte;
cout << fixed;
cout << setprecision(6) << distMinPunctePlanRec(puncte, 0, puncte.size(), puncteY) << "\n";
}
int main()
{
distMinPunctePlan();
return 0;
}