Pagini recente » Cod sursa (job #2642321) | Cod sursa (job #2956434) | Cod sursa (job #790597) | Cod sursa (job #3155252) | Cod sursa (job #2494793)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cfloat>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
struct Point{
double x, y;
};
int cmpX(const Point a, const Point b) {
if(a.x != b.x)
return (a.x < b.x);
return (a.y < b.y);
}
int cmpY(const Point a, const Point b) {
if(a.y != b.y)
return (a.y < b.y);
return (a.x < b.x);
}
double getdist(Point a, Point b) {
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double mindist3(Point v[], int n) {
double min_d = DBL_MAX;
for(int i = 0; i < n; ++i)// try < n - 1 if shit happens
for(int j = i + 1; j < n; ++j)
if(min_d > getdist(v[i], v[j]))
min_d = getdist(v[i], v[j]);
return min_d;
}
double minInStrip(Point strip[], int n, double d) {
double min_d = d;
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n && (strip[j].y - strip[i].y) < min_d; ++j)
if(getdist(strip[i], strip[j]) < min_d)
min_d = getdist(strip[i], strip[j]);
return min_d;
}
double closestDistance(Point X[], Point Y[], int n) {
if(n <= 3)
return mindist3(X, n);
int mid = n/2;
Point midp = X[mid];
Point Yleft[mid + 1], Yright[n - mid - 1];
int li = 0, ri = 0;
for(int i = 0; i < n; ++i) {
if(Y[i].x < midp.x)
Yleft[li++] = Y[i];
else
Yright[ri++] = Y[i];
}
double dleft = closestDistance(X, Yleft, mid);
double dright = closestDistance(X + mid, Yright, n - mid);
double d = min(dleft, dright);
Point strip[n];
int nr = 0;
for(int i = 0; i < n; ++i)
if(abs(Y[i].x - midp.x) < d)
strip[nr++] = Y[i];
return min(d, minInStrip(strip, nr, d));
}
double closestPair(Point v[], int n) {
Point X[n], Y[n];
for(int i = 0; i < n; ++i) {
X[i] = v[i];
Y[i] = v[i];
}
sort(X, X + n, cmpX);
sort(Y, Y + n, cmpY);
return closestDistance(X, Y, n);
}
int main() {
int n;
fin >> n;
Point points[n];
for(int i = 0; i < n; ++i) {
double a, b;
fin >> a >> b;
points[i] = {a, b};
}
cout << closestPair(points, n);
return 0;
}