Pagini recente » Cod sursa (job #1740655) | Cod sursa (job #1619894) | Cod sursa (job #1588141) | Cod sursa (job #2889064) | Cod sursa (job #1448143)
/*
* 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 pair<int, int> Point;
int N;
vector<Point> points;
double points_dist(Point& p1, Point& p2)
{
int x1 = p1.first, y1 = p1.second;
int x2 = p2.first, y2 = p2.second;
int dx = x1 - x2, dy = y1 - y2;
return sqrt(dx * dx + dy * dy);
}
double join_min_dist_in_set(int a, int m, int b, double dist)
{
//build the set Y1
vector<Point> Y1;
int my1 = m;
while (points[m + 1].first - points[my1].first <= dist)
{
Point p1;
p1.first = points[my1].second;
p1.second = points[my1].first;
Y1.push_back(p1);
my1--;
}
//build the set Y2
vector<Point> Y2;
int my2 = m + 1;
while (points[my2].first - points[m].first <= dist)
{
Point p2;
p2.first = points[my2].second;
p2.second = points[my2].first;
Y2.push_back(p2);
my2++;
}
//sorts the sets Y1 and Y2
std::sort(Y1.begin(), Y1.end());
std::sort(Y2.begin(), Y2.end());
// for each point in the set Y1, find the closest point in the set Y2, which should be
// smaller than the minimum distance computed so far
int sz1 = Y1.size();
int sz2 = Y2.size();
double min_inter_dist = std::numeric_limits<double>::max();
int i2_i1_start = 0;
for (int i1 = 0; i1 < sz1; i1++)
{
int i2 = i2_i1_start;
while (i2 < sz2 && points_dist(Y1[i1], Y2[i2]) >= dist)
i2++;
if (i2 < sz2) //we have found at least a point in Y2 such that dist(y1, y2) < dist
{
//save the new i2_i1_start
i2_i1_start = i2;
//start finding the minimum
int i3 = i2;
double dist13;
while (i3 < sz2 && (dist13 = points_dist(Y1[i1], Y2[i3])) <= dist)
{
min_inter_dist = min(min_inter_dist, dist13);
i3++;
}
}
}
return min(dist, min_inter_dist);
}
double min_dist_in_set(int a, int b)
{
if (b - a + 1 <= 3) //2 or 3 numbers; 1 not reachable by design
{
double min_dist = std::numeric_limits<double>::max();
for (int i = a; i <= b; i++)
for (int j = a; j <= b; j++)
if (j != i) min_dist = min(min_dist, points_dist(points[i], points[j]));
return min_dist;
}
//otherwise
//divide et impera
int m = (a + b) / 2;
double dist1 = min_dist_in_set(a, m);
double dist2 = min_dist_in_set(m + 1, b);
//join (impera)
double dist_ = min(dist1, dist2);
return join_min_dist_in_set(a, m, b, dist_);
}
}
int main()
{
using namespace e_046_cmap_nms;
ifstream ifs("cmap.in");
ifs >> N;
points.resize(N);
for (int i = 0; i < N; i++)
ifs >> points[i].first >> points[i].second;
ifs.close();
//sort the points
std::sort(points.begin(), points.end());
double min_dist = min_dist_in_set(0, N - 1);
ofstream ofs("cmap.out");
ofs.precision(10);
ofs << min_dist << endl;
ofs.close();
return 0;
}