Pagini recente » Cod sursa (job #2034689) | Istoria paginii runda/20_februarie_simulare_oji_2024_clasele_11_12/clasament | Cod sursa (job #987145) | Cod sursa (job #698528) | Cod sursa (job #2071336)
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
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); //calculating distance by euclidean formula
dist = sqrt(dist); //sqrt is function in math.h
return dist;
}
double distMinPunctePlanRec(vector <punct> & puncte, int st, int dr, vector<punct> &puncteY) {
if (dr-st == 1) {
return 2147483647; //int_max
}
if (dr-st == 2) {
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);
//construim banda
vector <punct> banda;
for (int i = 0; i < puncteY.size(); ++i) {
if (abs(puncteY[i].x - puncte[m].x) <= distMinStDr)
banda.push_back(puncteY[i]);
}
//rezolvam banda
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;
}
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;
}
void distMinPunctePlan() {
int n;
in >> n;
vector <punct> puncte(n);
for (int i = 0; i < n; ++i) {
in >> puncte[i].x;
in >> puncte[i].y;
}
sort(puncte.begin(), puncte.end(), cmpDupaX);
vector <punct> puncteY = puncte;
sort(puncteY.begin(), puncteY.end(), cmpDupaY);
out << fixed;
out << setprecision(6) << distMinPunctePlanRec(puncte, 0, puncte.size(), puncteY) << "\n";
}
int main()
{
distMinPunctePlan();
return 0;
}