Pagini recente » Cod sursa (job #502467) | Cod sursa (job #1489767) | Cod sursa (job #1700643) | Cod sursa (job #1818893) | Cod sursa (job #2104630)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define X first
#define Y second
using namespace std;
typedef pair<long long, long long> point;
vector<point> points;
void read() {
ifstream in("cmap.in");
int n;
long long x, y;
for (in >> n; n; --n) {
in >> x >> y;
points.push_back(make_pair(x, y));
}
in.close();
}
bool compareY(const point &p1, const point &p2) {
return (p1.Y <= p2.Y);
}
long long dist(const point& p1, const point &p2) {
return (p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y);
}
long long bruteMinDist(int left, int right) {
long long minValue = 0;
for (int i = left; i < right; i++)
for (int j = i + 1; j <= right; j++) {
if (minValue == 0)
minValue = dist(points[i], points[j]);
else
minValue = min(minValue, dist(points[i], points[j]));
}
return minValue;
}
long long stripMinDist(const vector<point>& strip, long long delta) {
long long minDist = delta;
for (unsigned int i = 0; i < strip.size(); i++)
for (unsigned int j = i + 1; j < strip.size() && (strip[i].Y - strip[j].Y) * (strip[i].Y - strip[j].Y) <= delta; j++)
minDist = min(minDist, dist(strip[i], strip[j]));
return minDist;
}
long long mergeSort(int left, int right) {
if (right - left <= 2) {
sort(points.begin() + left, points.begin() + right + 1, compareY);
return bruteMinDist(left, right);
} else {
int mid = left + (right - left) / 2;
long long midX = points[mid].X;
long long dist1 = mergeSort(left, mid);
long long dist2 = mergeSort(mid + 1, right);
long long delta = min(dist1, dist2);
/** Merging the points **/
vector<point> result;
result.resize(right - left + 1);
merge(points.begin() + left, points.begin() + mid + 1, points.begin() + mid + 1, points.begin() + right + 1, result.begin(), compareY);
copy(result.begin(), result.end(), points.begin() + left);
/** Building the strip **/
vector<point> strip;
for (int i = left; i <= right; i++)
if ((midX - points[i].X) * (midX - points[i].X) <= delta)
strip.push_back(points[i]);
long long dist3 = stripMinDist(strip, delta);
return min(delta, dist3);
}
}
int main() {
read();
sort(points.begin(), points.end());
long long minDist = mergeSort(0, points.size() - 1);
ofstream out("cmap.out");
out << fixed << setprecision(6) << sqrt(minDist) << "\n";
out.close();
return 0;
}