Pagini recente » Cod sursa (job #3263709) | Cod sursa (job #720861) | Cod sursa (job #693765) | Cod sursa (job #481878) | Cod sursa (job #1275280)
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
inline double dist(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
long long d1 = ((long long) a.first) - ((long long) b.first);
long long d2 = ((long long) a.second) - ((long long) b.second);
return sqrt(d1 * d1 + d2 * d2);
}
std::vector<std::pair<int, int> >read_data()
{
std::ifstream in("cmap.in");
int n, x, y;
std::vector<std::pair<int, int> > ret;
in >> n;
while (n--)
{
in >> x >> y;
ret.push_back(std::pair<int, int>(x, y));
}
in.close();
return ret;
}
void write_data(double sol)
{
std::ofstream out("cmap.out");
out << std::setprecision(6) << std::fixed << sol << '\n';
out.close();
}
double algo(const std::vector<std::pair<int, int> > &points, int left, int right)
{
if (right - left < 5)
{
double d = dist(points[left], points[left + 1]);
for (int i = left; i < right - 1; i++)
for (int j = i + 1; j < right; j++)
{
if (dist(points[i], points[j]) < 1510278)
std::cout << points[i].first << ' ' << points[i].second << ' ' << points[j].first << ' ' << points[j].second << ' ' << std::setprecision(10) << dist(points[i], points[j]) << '\n';
d = std::min(d, dist(points[i], points[j]));
}
return d;
}
int m = left + (right - left) / 2, dist1 = algo(points, left, m), dist2 = algo(points, m + 1, right);
double d = std::min(dist1, dist2);
std::vector<std::pair<int, int> > tmp;
for (int i = left; i < right; i++)
if (dist(points[i], points[m]) < d)
tmp.push_back(points[i]);
for (int i = 0; i < (int) tmp.size() - 1; i++)
for (int j = i + 1; j < std::min((int) tmp.size(), i + 8); j++)
if (i != j)
{
if (dist(tmp[i], tmp[j]) < 1510278)
{
std::cout << tmp[i].first << ' ' << tmp[i].second << ' ' << tmp[j].first << ' ' << tmp[j].second << ' ' << dist(tmp[i], tmp[j]) << '\n';
}
d = std::min(d, dist(tmp[i], tmp[j]));
}
return d;
}
bool mysort(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
if (a.first < b.first)
return true;
if (a.first == b.first)
return a.second < b.second;
return false;
}
int main()
{
std::vector<std::pair<int, int> > points = read_data();
std::sort(points.begin(), points.end(), mysort);
write_data(algo(points, 0, points.size()));
}