Pagini recente » Cod sursa (job #253064) | Cod sursa (job #1857106) | Cod sursa (job #1586211) | Cod sursa (job #1592970) | Cod sursa (job #3271243)
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <climits>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const long long INF = LLONG_MAX/4;
struct Point
{
long long x = 0;
long long y = 0;
};
long long dist(Point a, Point b)
{
return ((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
bool compx(Point a, Point b)
{
return (a.x < b.x);
}
bool compy(Point a, Point b)
{
return (a.y < b.y);
}
long long div_et_imp(vector<Point> &px, vector<Point> &py, vector<Point> &pseged, int left, int right)
{
if(right - left < 2){
return INF;
}
else if(right - left == 2){
if(py[left].y > py[left+1].y){
Point temp = py[left];
py[left] = py[left+1];
py[left+1] = temp;
}
return dist(px[left], px[left+1]);
}
int mid = (left + right)/2;
long long best = min(div_et_imp(px, py, pseged, left, mid), div_et_imp(px, py, pseged, mid, right));
merge(py.begin() + left, py.begin() + mid, py.begin() + mid, py.begin() + right, pseged.begin(), compy);
copy(pseged.begin(), pseged.begin() + (right - left), py.begin() + left);
int nr_points = 0;
for(int i = left; i < right; i++){
if(abs(px[mid].x - py[i].x) <= best){
pseged[nr_points] = py[i];
nr_points++;
}
}
for(int i = 0; i < nr_points-1; i++){
for(int j = i+1; j < nr_points && j-i < 8; j++){
best = min(best, dist(pseged[i], pseged[j]));
}
}
return best;
}
int main()
{
int n;
fin >> n;
vector<Point> px(n), py(n), pseged(n);
for(int i = 0; i < n; i++){
fin >> px[i].x >> px[i].y;
}
sort(px.begin(), px.end(), compx);
for(int i = 0; i < n; i++){
py[i] = px[i];
}
fout << fixed << setprecision(6) << sqrt(div_et_imp(px, py, pseged, 0, n));
return 0;
}