Pagini recente » Cod sursa (job #1292393) | Cod sursa (job #152675) | Cod sursa (job #1079517) | Cod sursa (job #1792111) | Cod sursa (job #2233589)
#include<fstream>
#include<vector>
#include<bitset>
#include<string.h>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<iomanip>
#include <iterator>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
typedef pair<long long, long long> Point;
int N;
Point points[100010];
vector<Point> mrg[100010 * 5];
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, int k)
{
if (y - x > 3)
{
int mid = (x + y) / 2;
double d1 = closest_pair_of_points(x, mid, k*2);
double d2 = closest_pair_of_points(mid + 1, y, k*2+1);
merge(mrg[k * 2].begin(), mrg[k * 2].end(), mrg[k * 2 + 1].begin(), mrg[k * 2 + 1].end(), back_inserter(mrg[k]));
double d = min(d1, d2);
vector<Point> vec;
for (int i=0;i<mrg[k].size();++i)
{
if (abs(points[mid].first - mrg[k][i].second) <= d)
vec.push_back(make_pair(mrg[k][i].second, mrg[k][i].first));
}
double f_d = 1LL<<60;
for(int i=0;i<vec.size();++i)
for (int j = i + 1; j < min(i + 8, (int)vec.size()); ++j)
{
f_d = min(f_d, distance(vec[i], vec[j]));
}
return min(d,f_d);
}
else
{
for (int i = x; i <= y; ++i)
mrg[k].push_back(make_pair(points[i].second, points[i].first));
sort(mrg[k].begin(), mrg[k].end());
double dist =1ll<<60;
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.sync_with_stdio(false);
in.tie(NULL);
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, 1);
return 0;
}