Pagini recente » Cod sursa (job #2454008) | Cod sursa (job #826782) | Cod sursa (job #1136188) | Cod sursa (job #1717292) | Cod sursa (job #1310711)
#include <fstream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iomanip>
#define INF 1000000002
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Point {
double x, y;
Point(int t, int u) {
x = t; y = u;
}
};
double dist(Point a, Point b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
bool cmp(Point a, Point b) {
return a.y<b.y;
}
int n;
vector<Point> A;
double dmin(int ls, int ld) {
if(ls == ld) return INF;
if(ld == ls+1) return dist(A[ls], A[ld]);
int mid = (ls+ld)/2;
double MIN = min(dmin(ls, mid), dmin(mid+1, ld));
for(int i1 = mid; A[i1].y>A[mid].y-MIN && i1; i1--) {
for(int i2 = mid+1; A[i2].y<A[mid].y+MIN && i2<n; i2++) {
MIN = min(MIN, dist(A[i1], A[i2]));
}
}
return MIN;
}
int main()
{
int a,b;
fin>>n;
for(int i=1; i<=n; i++) {
fin>>a>>b;
A.push_back(Point(a,b));
}
sort(A.begin(), A.end(), cmp);
fout<<setprecision(20)<<dmin(0, n-1);
return 0;
}