Pagini recente » Cod sursa (job #1771749) | Cod sursa (job #1718864) | Cod sursa (job #1920764) | Cod sursa (job #364037) | Cod sursa (job #809314)
Cod sursa(job #809314)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const long long INF = 4e18;
struct point
{
int x, y;
point(int abscissa, int ordinate)
{
x = abscissa;
y = ordinate;
}
friend bool operator< (point a, point b);
};
bool operator< (point a, point b)
{
if(a.x < b.x)
return true;
if(a.x == b.x)
return a.y < b.y;
return false;
}
bool is_below(point a, point b)
{
if(a.y < b.y)
return true;
if(a.y == b.y)
return (a.x < b.x);
return false;
}
point make_point(int abscissa, int ordinate)
{
point p(abscissa, ordinate);
return p;
}
long long distance_squared(point a, point b)
{
return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}
struct plane
{
private:
vector<point> points;
vector<point> y_order_points;
public:
void push_point(int abscissa, int ordinate)
{
points.push_back(make_point(abscissa, ordinate));
}
float distance_between_closest_points()
{
sort(points.begin(), points.end());
y_order_points = points;
return sqrt(cmap(0, points.size()));
}
private:
long long cmap(int left, int right)
{
if(right - left <= 1)
return INF;
if(right - left == 2)
{
if(is_below(y_order_points[left + 1], y_order_points[left]))
swap(y_order_points[left], y_order_points[left + 1]);
return distance_squared(points[left], points[left + 1]);
}
int mid = (left + right)/2;
long long best = min(cmap(left, mid), cmap(mid, right));
sort(y_order_points.begin() + left, y_order_points.begin() + right, is_below);
vector<point> v;
for(int i = left; i < right; ++i)
if(abs(y_order_points[i].x - points[mid].x) <= best)
v.push_back(y_order_points[i]);
for(int i = 0; i < v.size(); ++i)
for(int j = i + 1; j < v.size() && j - i < 8; ++j)
best = min(best, distance_squared(v[i], v[j]));
return best;
}
};
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
int N;
in >> N;
plane P;
for(int i = 0, x, y; i < N; ++i)
{
in >> x >> y;
P.push_point(x, y);
}
out << fixed << P.distance_between_closest_points();
in.close();
out.close();
return 0;
}