Pagini recente » Cod sursa (job #440509) | Cod sursa (job #1375822) | Cod sursa (job #1775905) | Istoria paginii runda/zxzx._jskds/clasament | Cod sursa (job #2492703)
#include <vector>
#include <utility>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct Punct{
long int first, second;
};
long int dist(Punct A, Punct B){
long int d= (B.first - A.first) * (B.first - A.first) + (B.second - A.second) * (B.second - A.second);
return d;
}
bool compx(Punct A, Punct B){
if(A.first != B.first)
return A.first < B.first;
return A.second < B.second;
}
bool compy(Punct A, Punct B){
if(A.second != B.second)
return A.second < B.second;
return A.first < B.first;
}
vector<Punct>points;
int dist_min(int stg, int drp){
if(drp - stg +1 == 3){
return min( dist(points[stg], points[stg+1]), min(dist(points[stg], points[drp]), dist(points[stg+1], points[drp])));
}
if(drp - stg +1 == 2){
return dist(points[stg], points[drp]);
}
int mid = (stg + drp) / 2;
long int ds, dd, d;
ds = dist_min(stg, mid);
dd = dist_min(mid+1, drp);
d = min(ds, dd);
double x = sqrt(d);
vector<Punct> y;
for(int i = stg; i<=drp; i++)
if(points[mid].first - x <= points[i].first && points[mid].first + x >= points[i].first)
y.push_back(points[i]);
sort(y.begin(), y.end(), compy);
for(unsigned int i=0; i<y.size(); i++)
for(unsigned int j= i+1; j<y.size() && j<=i+7; j++){
d = min(dist(y[i], y[j]), d);
}
return d;
}
int main()
{
int n;
f>>n;
for(int i=0; i<n; i++)
{
Punct p;
f>>p.first>>p.second;
points.push_back(p);
}
sort(points.begin(), points.end(), compx);
g << fixed << setprecision(6)<< sqrt(dist_min(0, n-1));
return 0;
}