Pagini recente » Cod sursa (job #1448339) | Cod sursa (job #1489125) | Cod sursa (job #1545628) | Cod sursa (job #1025974) | Cod sursa (job #1618453)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
long int n;
typedef struct Point {
long int x;
long int y;
} Point;
vector<Point> pVector;
#define INF 0x7fffffff
void read() {
ifstream fin("cmap.in");
long int x, y;
fin >> n;
while (fin >> x >> y) {
Point p;
p.x = x;
p.y = y;
pVector.push_back(p);
}
fin.close();
}
bool wayToSortX (Point i, Point j) {
return i.x < j.x;
}
bool wayToSortY (Point i, Point j) {
return i.y < j.y;
}
void sortX() {
sort(pVector.begin(), pVector.end(), wayToSortX);
}
void display() {
for (int i = 0; i < n; i++)
cout << pVector[i].x << " " << pVector[i].y << endl;
getchar();
}
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(int left, int right) {
double d = INF;
for (int i = left; i < right - 1; i++)
for (int j = i + 1; j < right; j++)
d = min(d, distance(pVector[i], pVector[j]));
}
long double findMinDistance(int start, int end) {
if (end - start <= 2)
return threePoints(start, end);
int mid = (start + end) / 2;
double d = min(findMinDistance(start, mid), findMinDistance(mid + 1, end));
int xmid = pVector[n / 2].x;
vector<Point> midRegion;
for (int i = 0; i < n / 2; i++) {
if (abs(pVector[i].x - xmid) < d)
midRegion.push_back(pVector[i]);
}
for (int i = n / 2; i < n; i++) {
if (abs(pVector[i].x - xmid) < d)
midRegion.push_back(pVector[i]);
}
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()
{
std::ofstream fout("cmap.out");
read();
sortX();
fout << std::fixed << findMinDistance(0, n - 1) << '\n';
return 0;
}