Pagini recente » Cod sursa (job #762666) | Cod sursa (job #2493985) | Cod sursa (job #1241927) | Cod sursa (job #2430431) | Cod sursa (job #2492614)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
struct point {
double x, y;
};
bool cmpX(point a, point b) {
if (a.x > b.x) return 1;
return 0;
}
bool cmpY(point a, point b) {
if (a.y > b.y) return 1;
return 0;
}
double twoPointsDistance(point a, point b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double minDistance(vector <point> pt, int left, int right) {
int separator = (left + right) / 2;
double delta = 2e9;
if (right - left > 2)
delta = min (minDistance(pt, left, separator), minDistance(pt, separator + 1, right));
else
for(int i = left; i < right; ++i)
for (int j = i + 1; j <= right; ++j) {
double distance = twoPointsDistance(pt[i], pt[j]);
if (distance < delta) delta = distance;
}
vector <point> eligiblePoints;
for (int i = left; i <= right; ++i)
if (abs(pt[i].x - pt[separator].x) < delta)
eligiblePoints.push_back(pt[i]);
sort(eligiblePoints.begin(), eligiblePoints.end(), cmpY);
int n = eligiblePoints.size();
for (int i = 0; i < n; ++i) {
int m = min(n, i + 8);
for (int j = i + 1; j < m; ++j) {
double distance = twoPointsDistance(eligiblePoints[i], eligiblePoints[j]);
if (distance < delta)
delta = distance;
}
}
return delta;
}
int main()
{
int n;
vector <point> pt;
cin >> n;
for (int i = 0; i < n; ++i) {
point x;
cin >> x.x >> x.y;
pt.push_back(x);
}
sort(pt.begin(), pt.end(), cmpX);
double minimumDistance = minDistance(pt, 0, n - 1);
//cout << twoPointsDistance(pt[8], pt[9]);
cout << fixed << setprecision(6) << minimumDistance;
}