Pagini recente » Cod sursa (job #3208537) | Cod sursa (job #1752351) | Cod sursa (job #2173096) | Cod sursa (job #1413919) | Cod sursa (job #808717)
Cod sursa(job #808717)
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define INF 1000000000
using namespace std;
class plane
{
private:
vector<pair<int, int> > points;
public:
void push(int x, int y)
{
points.push_back(make_pair(x, y));
}
float distance_between_closest_points()
{
sort(points.begin(), points.end());
return cpd(0, points.size() - 1);
}
private:
float distance(pair<int, int>a, pair<int, int> b)
{
return sqrt(pow(b.first - a.first, 2) + (float)pow(b.second - a.second, 2));
}
float cpd(int left, int right)
{
int mid = (left + right)/2;
if(left == right)
return INF;
if(right - left == 1)
return distance(points[left], points[right]);
float min_left = cpd(left, mid);
float min_right = cpd(mid + 1, right);
float min_sides = min(min_left, min_right);
for(int i = mid; i >= 0 && points[i].first > points[mid].first - min_sides; --i)
{
for(int j = mid; j < points.size() && points[j].first < points[mid].first + min_sides; ++j)
{
if(points[j].second < points[i].second + min_sides && points[i].second - min_sides < points[j].second)
{
float temp_dis = distance(points[i], points[j]);
if(temp_dis > min_sides)
min_sides = temp_dis;
}
}
}
return min_sides;
}
};
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
plane my_plane;
int N;
in >> N;
for(int i = 0, x, y; i < N; ++i)
{
in >> x >> y;
my_plane.push(x, y);
}
out.precision(1000);
out << my_plane.distance_between_closest_points();
in.close();
out.close();
}