Pagini recente » Cod sursa (job #406429) | Cod sursa (job #1079664) | Cod sursa (job #1049643) | Cod sursa (job #896525) | Cod sursa (job #2495533)
/*
Sample input:
10
26 77
12 37
14 18
19 96
71 95
91 9
98 43
66 77
2 75
94 91
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdint>
using namespace std;
struct Punct {
int x, y;
};
bool ComparaAbscise(Punct A, Punct B) {
return A.x < B.x;
}
bool ComparaOrdonate(Punct A, Punct B) {
return A.y < B.y;
}
inline int distantaPatrata(Punct A, Punct B) {
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
inline float distanta(Punct A, Punct B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
float cmap(int pozStart, int pozSfarsit, const vector<Punct> &Puncte) {
if (pozSfarsit - pozStart <= 3) {
float distMin = INT32_MAX;
for (int i = pozStart; i <= pozSfarsit - 1; i++)
for (int j = i + 1; j <= pozSfarsit; j++)
distMin = min(distMin, distanta(Puncte[i], Puncte[j]));
return distMin;
}
int dreapta = (pozSfarsit + pozStart) / 2;
float minimStanga = cmap(pozStart, dreapta, Puncte);
float minimDreapta = cmap(dreapta + 1, pozSfarsit, Puncte);
float minimGlobal = min(minimStanga, minimDreapta);
// Merge
vector<Punct> PuncteApropiate;
PuncteApropiate.push_back(Puncte[dreapta]);
int currentX = Puncte[dreapta].x;
// Stanga
for (int poz = dreapta - 1, delta = currentX - Puncte[dreapta - 1].x; delta <= minimGlobal && poz >= 0; poz--) {
PuncteApropiate.push_back(Puncte[poz]);
delta = currentX - Puncte[poz].x;
}
// Dreapta
for (int poz = dreapta + 1, delta = Puncte[dreapta + 1].x - currentX; delta <= minimGlobal && poz < Puncte.size(); poz++) {
PuncteApropiate.push_back(Puncte[poz]);
delta = Puncte[poz].x - currentX;
}
// Aici ar trebui facuta interclasare
sort(PuncteApropiate.begin(), PuncteApropiate.end(), ComparaOrdonate);
// Determinare minim intre submultimi
int distMin = INT32_MAX;
int distPozVerificari = min(7, (int)PuncteApropiate.size() - 1);
for (int i = 0; i < PuncteApropiate.size() - distPozVerificari; i++)
for (int j = i + 1; j <= i + distPozVerificari && j < PuncteApropiate.size(); j++)
distMin = min(distMin, distantaPatrata(PuncteApropiate[i], PuncteApropiate[j]));
return min(minimGlobal, sqrtf(distMin));
}
int problema_4(ifstream &in, ofstream &out) {
vector<Punct> Puncte;
int n;
in >> n;
Puncte.resize(n);
for (auto &Punct : Puncte)
in >> Punct.x >> Punct.y;
sort(Puncte.begin(), Puncte.end(), ComparaAbscise);
out << cmap(0, Puncte.size() - 1, Puncte);
return 0;
}
int main() {
ifstream in("date.in");
ofstream out("date.out");
if (!in || !out)
return 1;
problema_4(in, out);
in.close();
out.close();
return 0;
}