Pagini recente » Istoria paginii runda/lot2015-baraj5 | Cod sursa (job #1214044) | Cod sursa (job #71696) | Cod sursa (job #963800) | Cod sursa (job #2492641)
#include <iostream>
#include <vector>
#include <utility>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
int dist(pair<int, int> A, pair<int, int> B){
int d= (B.first - A.first) * (B.first - A.first) + (B.second - A.second) * (B.second - A.second);
return d;
}
bool compx(pair<int, int> A, pair<int, int> B){
if(A.first != B.first)
return A.first < B.first;
else
return A.second < B.second;
}
bool compy(pair<int, int> A, pair<int, int> B){
return A.second < B.second;
}
int dist_min(vector<pair<int,int>>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<pair<int, int>> 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<=7; j++){
d = min(dist(y[i], y[j]), d);
}
return d;
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
int x, y, n;
f>>n;
vector<pair<int,int>>points;
for(int i=0; i<n; i++)
{
f>>x>>y;
points.push_back(make_pair(x,y));
}
sort(points.begin(), points.end(), compx);
int d= dist_min(points, 0, n-1);
g << fixed << setprecision(6)<< sqrt(d);
return 0;
}