Pagini recente » Cod sursa (job #79717) | Cod sursa (job #2282458) | Cod sursa (job #621114) | Cod sursa (job #2894345) | Cod sursa (job #1448372)
/*
* e_046_cm_apropiate_puncte.cpp
*
* Created on: Jun 6, 2015
* Author: Marius
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <utility>
using namespace std;
namespace e_046_cmap_nms
{
typedef long long sll;
typedef pair<sll, sll> Point;
int N;
vector<Point> X;
vector<Point> Y;
vector<Point> V;
vector<Point> S;
sll points_dist(Point& p1, Point& p2)
{
sll x1 = p1.first, y1 = p1.second;
sll x2 = p2.first, y2 = p2.second;
sll dx = x1 - x2, dy = y1 - y2;
return dx * dx + dy * dy;
}
sll min_dist_in_set(int a, int b, vector<Point>& Y)
{
if (b - a == 0) return std::numeric_limits<sll>::max();
if (b - a == 1)
{
//also sort the the points in Y by the Y coordinates
if (Y[a] > Y[b]) swap(Y[a], Y[b]);
return points_dist(X[a], X[b]);
}
//otherwise
//divide et impera
int m = (a + b) / 2;
sll dist1 = min_dist_in_set(a, m, Y);
sll dist2 = min_dist_in_set(m + 1, b, Y);
//join (impera)
sll dist_ = min(dist1, dist2);
//Y-sorted between a and m
//Y-sorted between m+1 and b
//should be interleaved between a and b
//...but I'am lazy and I sort them again
//std::sort(Y.begin() + a, Y.begin() + b + 1);
//...but only 70 points
//interleave
int i1 = a, i2 = m + 1;
int k = a;
while (i1 <= m && i2 <= b)
if (Y[i1] <= Y[i2]) S[k++] = Y[i1++];
else S[k++] = Y[i2++];
while (i1 <= m) S[k++] = Y[i1++];
while (i2 <= b) S[k++] = Y[i2++];
//copy the elements back to Y
for (int i = a; i <= b; i++) Y[i] = S[i];
//find the elements in Y that are close to the vertical axis between x[m] and x[m+1]
int vsize = 0;
for (int i = a; i <= b; i++)
if (abs(Y[i].second - X[m].first) <= dist_) V[vsize++] = Y[i];
for (int i = 0; i < vsize; i++)
for (int j = i + 1; j <= i + 7 && j < vsize; j++)
dist_ = min(dist_, points_dist(V[i], V[j]));
return dist_;
}
}
int main()
{
using namespace e_046_cmap_nms;
ifstream ifs("cmap.in");
ifs >> N;
X.resize(N);
Y.resize(N);
V.resize(N);
S.resize(N);
for (int i = 0; i < N; i++)
{
ifs >> X[i].first >> X[i].second;
Y[i].first = X[i].second;
Y[i].second = X[i].first;
}
ifs.close();
//sort the points on the x-axis
std::sort(X.begin(), X.end());
sll min_dist = min_dist_in_set(0, N - 1, Y);
ofstream ofs("cmap.out");
ofs.precision(6);
ofs << fixed;
ofs << sqrt(min_dist + 0.0) << endl;
ofs.close();
return 0;
}