Pagini recente » Cod sursa (job #844190) | Cod sursa (job #333968) | Cod sursa (job #553681) | Cod sursa (job #963775) | Cod sursa (job #2492653)
#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{
int first, second;
};
int dist(Punct A, Punct B){
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){
return A.first < B.first;
}
bool compy(Punct A, Punct B){
return A.second < B.second;
}
int dist_min(vector<Punct>points, 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;
int ds, dd, d;
ds = dist_min(points, stg, mid);
dd = dist_min(points, mid+1, drp);
d = min(ds, dd);
double x = sqrt(d);
vector<Punct> y;
for(int i = stg; i<=drp; i++)
if(abs(points[mid].first - points[i].first) <= x)
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++){
int rez= dist(y[i], y[j]);
d = min(rez, d);
}
return d;
}
int main()
{
int n;
f>>n;
vector<Punct>points;
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(points, 0, n-1));
return 0;
}