Pagini recente » Monitorul de evaluare | Cod sursa (job #2555856) | Cod sursa (job #2430846) | Cod sursa (job #2555145) | Cod sursa (job #2104612)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> point;
vector<point> points;
void read() {
ifstream in("cmap.in");
int n, 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);
}
int dist(const point& p1, const point &p2) {
return (p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y);
}
int bruteMinDist(int left, int right) {
int 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;
}
int stripMinDist(const vector<point>& strip, int delta) {
int 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;
}
int 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;
int dist1 = mergeSort(left, mid);
int dist2 = mergeSort(mid + 1, right);
int 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 ((points[mid].X - points[i].X) * (points[mid].X - points[i].X) <= delta)
strip.push_back(points[i]);
int dist3 = stripMinDist(strip, delta);
return min(delta, dist3);
}
}
int main()
{
read();
sort(points.begin(), points.end());
int minDist = mergeSort(0, points.size() - 1);
ofstream out("cmap.out");
out << sqrt(minDist) << "\n";
out.close();
return 0;
}