Pagini recente » Cod sursa (job #140423) | Cod sursa (job #2410624) | Cod sursa (job #1150307) | Cod sursa (job #2934297) | Cod sursa (job #2639362)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define EPSILON 1e-17
#define INF 1e9
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point {
int x, y;
};
vector<point> vec;
bool cmpX(const point& a,const point& b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool cmpY(const point& a,const point& b) {
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
double dist(point a, point b) {
long long int x = a.x - b.x;
long long int y = a.y - b.y;
x *= x;
y *= y;
return sqrt(x + y);
}
double closestPair(vector<point>& vec) {
sort(vec.begin(), vec.end(), cmpX);
set<point, decltype(cmpY)*> s(cmpY);
set<point, decltype(cmpY)*>::iterator it;
int i = 0;
double d = INF;
for (int j = 0;j < vec.size();++j) {
while (i<j && vec[j].x - vec[i].x>d) {
s.erase(vec[i]);
++i;
}
s.insert(vec[j]);
it = s.find(vec[j]);
set<point, decltype(cmpY)*>::iterator succ = next(it);
while (succ != s.end() && (*succ).y - vec[j].y < d) {
if (dist((*succ), vec[j]) < d) d = dist((*succ), vec[j]);
succ = next(succ);
}
set<point, decltype(cmpY)*>::iterator pred = prev(it);
while (pred != s.end() && vec[j].y - (*pred).y < d) {
if (dist((*pred), vec[j]) < d) d = dist((*pred), vec[j]);
pred = prev(pred);
}
}
return d;
}
int main()
{
int n;
fin >> n;
int x, y;
while (n--) {
fin >> x >> y;
vec.push_back({ x,y });
}
fout << fixed << setprecision(6);
fout<<closestPair(vec);
return 0;
}