Pagini recente » Cod sursa (job #210455) | Cod sursa (job #319861) | Cod sursa (job #2889359) | Cod sursa (job #1493496) | Cod sursa (job #3330740)
#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
{
if(x == other.x)
return (y < other.y);
return (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 solve(int st, int dr)
{
double ans = 1e18;
if(dr - st + 1 <= 3)
{
for(int i = st; i <= dr; i++)
for(int j = i + 1; j <= dr; j++)
ans = min(ans, dist(points[i], points[j]));
}
else
{
int mid = (st + dr) / 2;
vector<Point> sorted;
ans = min({ans, solve(st, mid), solve(mid + 1, dr)});
for(int i = st; i <= dr; i++)
{
double dif = abs(points[mid].x - points[i].x);
if(dif < ans)
sorted.push_back(points[i]);
}
sort(sorted.begin(), sorted.end(), [&] (Point A, Point B) { return (A.y < B.y); });
for(int i = 0; i < sorted.size(); i++)
for(int j = i + 1; j < sorted.size() && j - i <= 8; j++)
ans = min(ans, dist(sorted[i], sorted[j]));
}
return ans;
}
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) << solve(1, n);
fin.close();
fout.close();
return 0;
}