Pagini recente » Cod sursa (job #1012221) | Cod sursa (job #369872) | Cod sursa (job #270238) | Cod sursa (job #1736543) | Cod sursa (job #2489183)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <float.h>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct point
{
double x, y;
friend istream &operator >>(istream& in, point &a)
{
in >> a.x >> a.y;
return in;
}
friend ostream &operator <<(ostream& out, const point &a)
{
out << a.x << " " << a.y << "\n";
return out;
}
friend double dist_sq(const point& a, const point& b)
{
double first = (a.x - b.x) * (a.x - b.x);
double second = (a.y - b.y) * (a.y - b.y);
return double(first + second);
}
friend double dist(const point& a, const point& b)
{
return double(sqrt(dist_sq(a,b)));
}
};
int read(point * &v, ifstream &f)
{
int n;
point temp;
f >> n;
v = new point[n];
for (int i = 0; i < n; i++)
{
f >> temp;
v[i] = temp;
}
return n;
}
void afis(point *v, int size)
{
for (int i = 0; i < size; i++)
cout << v[i].x << " " << v[i].y << "\n";
cout << "\n";
}
bool comp_x(const point& a, const point& b)
{
return a.x < b.x;
}
bool comp_y(const point& a, const point& b)
{
return a.y < b.y;
}
double bruteForce(point* vp, int n)
{
double min = FLT_MAX;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (dist(vp[i], vp[j]) < min)
min = dist(vp[i], vp[j]);
return min;
}
double min(double x, double y)
{
return (x < y) ? x : y;
}
double stripClosest(point* strip, int size, double d)
{
double min = d;
sort(strip,strip+size, comp_y);
for (int i = 0; i < size; ++i)
for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j)
if (dist(strip[i], strip[j]) < min)
min = dist(strip[i], strip[j]);
return min;
}
double closestDivide(point *vp, int n)
{
if (n <= 3)
return bruteForce(vp, n);
int mid = n / 2;
point midp = vp[mid];
double minleft = closestDivide(vp, mid);
double minright = closestDivide(vp + mid, n - mid);
double d = min(minleft, minright);
point* strip = new point[n];
int j = 0;
for (int i = 0; i < n; i++)
if (abs(vp[i].x - midp.x) < d)
strip[j] = vp[i], j++;
return min(d, stripClosest(strip, j, d));
}
double closest(point *vp, int n)
{
sort(vp,vp+n,comp_x);
return closestDivide(vp, n);
}
int main()
{
int n;
point* v=new point[0];
n = read(v, f);
g<<setprecision(8)<<closest(v, n);
delete[]v;
}