Pagini recente » Cod sursa (job #1167149) | Cod sursa (job #988018) | Cod sursa (job #1494077) | Cod sursa (job #2180230) | Cod sursa (job #3331301)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMAX = 1e5 + 1;
struct Point
{
double x, y;
bool operator < (const Point &other) const
{
return (x == other.x ? y < other.y : x < other.x);
}
} points[NMAX];
double dist(Point A, Point B)
{
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
double closest_points(int st, int dr)
{
double dist_min = DBL_MAX;
if(dr - st + 1 <= 3)
{
for(int i = st; i <= dr; i++)
for(int j = i + 1; j <= dr; j++)
dist_min = min(dist_min, dist(points[i], points[j]));
for(int i = st; i <= dr; i++)
for(int j = i + 1; j <= dr; j++)
if(points[i].y > points[j].y)
swap(points[i], points[j]);
return dist_min;
}
int mid = (st + dr) / 2;
dist_min = min({dist_min, closest_points(st, mid), closest_points(mid + 1, dr)});
inplace_merge(points + st, points + mid, points + dr);
for(int i = st; i <= dr; i++)
for(int j = 1; j <= 7 && i + j <= dr; j++)
dist_min = min(dist_min, dist(points[i], points[i + j]));
return dist_min;
}
int main()
{
int n;
fin >> n;
for(int i = 1; i <= n; i++)
fin >> points[i].x >> points[i].y;
sort(points + 1, points + n + 1);
fout << fixed << setprecision(6) << closest_points(1, n);
fin.close();
fout.close();
return 0;
}