Pagini recente » Cod sursa (job #486689) | Cod sursa (job #2768611) | Cod sursa (job #1834861) | Cod sursa (job #171347) | Cod sursa (job #2233558)
#include<fstream>
#include<vector>
#include<bitset>
#include<string.h>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
typedef pair<int, int> Point;
int N;
Point points[100010];
double distance(const Point& p1, const Point& p2)
{
return sqrt((p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second));
}
double closest_pair_of_points(int x,int y)
{
if (y - x > 3)
{
int mid = (x + y) / 2;
double d1 = closest_pair_of_points(x, mid);
double d2 = closest_pair_of_points(mid + 1, y);
double d = min(d1, d2);
vector<Point> vec;
for (int i = x; i <= y; ++i)
{
if (distance(points[i], points[mid]) <= d)
vec.push_back(make_pair(points[i].second, points[i].first));
}
sort(vec.begin(), vec.end());
double f_d = 1 << 20;
for(int i=0;i<vec.size();++i)
for (int j = i + 1; j + 8 < vec.size(); ++j)
{
f_d = min(f_d, distance(vec[i], vec[j]));
}
return min(d,f_d);
}
else
{
double dist = 1 << 20;
for(int i=x;i<=y;i++)
for (int j = i + 1; j <= y; ++j)
{
dist = min(dist, distance(points[i], points[j]));
}
return dist;
}
}
int main()
{
in >> N;
for (int i = 1; i <= N; ++i)
{
int x, y;
in >> x >> y;
points[i] = { x,y };
}
sort(points + 1, points + N + 1);
out << fixed << setprecision(6) << closest_pair_of_points(1, N);
return 0;
}