Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/gabordragos | Monitorul de evaluare | Profil CristinaM | Cod sursa (job #2074069)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct point{
int x, y;
};
bool cmp(point a, point b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
long long d(point a, point b){
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
int n;
long long minDist(int l, int r, vector<point>& points){
if(r - l == 1)
return d(points[l], points[r]);
else if(r - l == 2){
return min(d(points[l], points[l + 1]), min(d(points[l], points[l + 2]), d(points[l + 1], points[l + 2])));
}
int mid = (l + r) / 2;
long long midL = minDist(l, mid, points);
long long midR = minDist(mid, r, points);
long long minD = min(midL, midR);
vector<point> aux;
for(int i = l; i < mid; i++)
if(abs(points[i].x - points[mid].x) < minD)
aux.push_back(points[i]);
for(int i = mid + 1; i <= r; i++)
if(abs(points[i].x - points[mid].x) < minD)
aux.push_back(points[i]);
for(int i = 0; i < (int)aux.size(); i++)
for(int j = 0; j < (int)aux.size(); j++)
if(j != i && d(aux[i], aux[j]) < minD)
minD = d(aux[i],aux[j]);
return minD;
}
int main()
{
vector<point> points;
f >> n;
for(int i = 0; i < n; i++){
point t;
f >> t.x >> t.y;
points.push_back(t);
}
sort(points.begin(), points.end(), cmp);
g << fixed << setprecision(6) << sqrt(minDist(0, n - 1, points));
return 0;
}