Pagini recente » Cod sursa (job #2531640) | Cod sursa (job #3357578) | Cod sursa (job #1018622) | Cod sursa (job #1499124) | Cod sursa (job #3352175)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct Punct {
double x, y;
};
// Functie pentru patratul distantei (mentine precizia si viteza)
double distSq(Punct p1, Punct p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
bool cmpX(const Punct &a, const Punct &b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
// Vector auxiliar global sau transmis prin referinta pentru interclasare
Punct temp[100005];
double rezolva(int st, int dr, vector<Punct> &P) {
// Caz de baza: distanta infinita sau calcul direct pentru 2-3 puncte
if (st >= dr) return 1e18;
if (dr - st == 1) {
if (P[st].y > P[dr].y) swap(P[st], P[dr]); // Sortam dupa Y pentru interclasare
return sqrt(distSq(P[st], P[dr]));
}
int mij = st + (dr - st) / 2;
double mijX = P[mij].x;
// Divide: calculam delta pentru cele doua jumatati
double delta = min(rezolva(st, mij, P), rezolva(mij + 1, dr, P));
// INTERCLASARE (Merge): sortam punctele dupa Y in O(n)
int i = st, j = mij + 1, k = st;
while (i <= mij && j <= dr) {
if (P[i].y < P[j].y) temp[k++] = P[i++];
else temp[k++] = P[j++];
}
while (i <= mij) temp[k++] = P[i++];
while (j <= dr) temp[k++] = P[j++];
for (i = st; i <= dr; i++) P[i] = temp[i];
// COMBINA: Construim banda centrala folosind punctele deja sortate dupa Y
vector<Punct> banda;
for (i = st; i <= dr; i++) {
if (abs(P[i].x - mijX) <= delta) {
banda.push_back(P[i]);
}
}
// Verificam regula celor 7 puncte
for (i = 0; i < banda.size(); i++) {
for (j = i + 1; j < banda.size() && (banda[j].y - banda[i].y) <= delta && (j - i) <= 7; j++) {
delta = min(delta, sqrt(distSq(banda[i], banda[j])));
}
}
return delta;
}
int main() {
ifstream fin("puncte.in");
ofstream fout("puncte.out");
int n;
if (!(fin >> n)) return 0;
vector<Punct> puncte(n);
for (int i = 0; i < n; i++) fin >> puncte[i].x >> puncte[i].y;
// Sortarea initiala dupa X este obligatorie
sort(puncte.begin(), puncte.end(), cmpX);
fout << fixed << setprecision(6) << rezolva(0, n - 1, puncte) << endl;
return 0;
}