Pagini recente » Cod sursa (job #1737658) | Cristelnita - Al eigiler un es etsebrov | Cod sursa (job #1735052) | Cod sursa (job #2472376) | Cod sursa (job #1618888)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
double n;
typedef struct Point {
double x;
double y;
} Point;
#define INF 0x7fffffff
bool wayToSortX (Point i, Point j) {
return i.x < j.x;
}
bool wayToSortY (Point i, Point j) {
return i.y < j.y;
}
double distance(Point p, Point q) {
return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}
double threePoints(vector<Point> v) {
double d = INF;
for (int i = 0; i < v.size() - 1; i++)
for (int j = i + 1; j < v.size(); j++)
d = min(d, distance(v[i], v[j]));
}
vector<Point> slice(vector<Point> v, int start, int end) {
vector<Point> nv;
nv.assign(v.begin() + start, v.begin() + end);
return nv;
}
double findMinDistance(vector<Point> v) {
if (v.size() <= 3)
return threePoints(v);
int mid = v.size() / 2;
int xmid = v[mid].x;
double d = min(findMinDistance(slice(v, 0, mid + 1)), findMinDistance(slice(v, mid + 1, v.size())));
int left, right;
left = mid;
right = mid;
while (abs(v[left].x - xmid) < d)
left--;
while (abs(v[right].x - xmid) < d)
right++;
vector<Point> midRegion = slice(v, left, right);
// sortez dupa y
sort(midRegion.begin(), midRegion.end(), wayToSortY);
for (int i = 0; i < midRegion.size(); i++)
for (int j = 1; j < 8; j++)
if (i + j < midRegion.size())
d = min(d, distance(midRegion[i], midRegion[i + j]));
return d;
}
int main()
{
ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
int x, y;
fin >> n;
vector<Point> pVector;
while (fin >> x >> y) {
Point p;
p.x = x;
p.y = y;
pVector.push_back(p);
}
fin.close();
// sortare dupa x a punctelor
sort(pVector.begin(), pVector.end(), wayToSortX);
cout << findMinDistance(pVector) << '\n';
return 0;
}