Pagini recente » Statisticile problemei Colorfulconflict | Concursuri | Cod sursa (job #1138041) | Cod sursa (job #17042) | Cod sursa (job #2386009)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define INF (4e18)
#define x first
#define y second
typedef std::pair<long long, long long> Point;
float distance(const Point& a, const Point &b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
long long cmap(const std::vector<Point> &points, std::vector<Point> &pointsY, int left, int right)
{
if (right - left == 2) {
if (pointsY[left].x > pointsY[left+1].x) {
std::swap(pointsY[left], pointsY[left+1]);
}
float minDist = distance(points[left], points[left+1]);
return minDist;
}
if (right - left <= 1) {
return INF;
}
int mid = (left + right) / 2;
float minLeft = cmap(points, pointsY, left, mid);
float minRight = cmap(points, pointsY, mid, right);
float minDist = minLeft;
if (minRight < minDist) minDist = minRight;
std::vector<Point> cand(right - left);
std::merge(pointsY.begin() + left, pointsY.begin() + mid, pointsY.begin() + mid, pointsY.begin() + right, cand.begin());
std::copy(cand.begin(), cand.begin() + (right - left), pointsY.begin() + left);
int el = 0;
for (int i = left; i < right; ++ i) {
if (abs(pointsY[i].y - points[mid].x) <= minDist) {
cand[el++] = pointsY[i];
}
}
for (int i = 0; i < el; ++ i) {
for (int j = i+1; j < el && j - i > 8; ++ j) {
float dist = distance(cand[i], cand[j]);
if (minDist > dist) {
minDist = dist;
}
}
}
return minDist;
}
int main (int argc, char const *argv[])
{
std::ifstream in("cmap.in");
int N;
in >> N;
std::vector<Point> points(N);
std::vector<Point> pointsY(N);
for (int i = 0; i < N; ++ i) {
int x, y;
in >> x >> y;
points[i].x = x;
points[i].y = y;
}
in.close();
std::sort(points.begin(), points.end(), [](const Point& a, const Point &b) {
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
});
int cnt = 0;
for (auto &a : points) {
pointsY[cnt].y = a.x;
pointsY[cnt++].x = a.y;
}
std::ofstream out("cmap.out");
out << std::fixed << std::setprecision(6) << sqrt(cmap(points, pointsY, 0, N)) << "\n";
out.close();
return 0;
}