Pagini recente » Cod sursa (job #1112397) | Cod sursa (job #3001058) | Cod sursa (job #1231760) | Cod sursa (job #1535795) | Cod sursa (job #1721106)
#include <bits/stdc++.h>
using namespace std;
struct punct{
double x, y; };
double dist(const punct& p1, const punct& p2){
return hypot(p1.x-p2.x, p1.y-p2.y); }
struct cmap_rez_t {
vector<punct> by_y;
double dist; };
auto cmp_by_y = [](const punct& p1, const punct& p2){
return p1.y < p2.y; };
cmap_rez_t cmap(vector<punct> v){
if(v.size() < 10){
double rez = dist(v[0], v[1]);
for(int i = 0; i < v.size(); ++i){
for(int j = i+1; j < v.size(); ++j){
rez = min(rez, dist(v[i], v[j])); } }
sort(begin(v), end(v), cmp_by_y);
return cmap_rez_t { move(v), rez }; }
const int n = v.size();
nth_element(begin(v), begin(v) + n/2, end(v), [](const punct& p1, const punct& p2){
return p1.x < p2.x; });
const double mid = v[n/2].x;
vector<punct> left(begin(v), begin(v)+n/2), right(begin(v)+n/2, end(v));
auto rez_left = cmap(left), rez_right = cmap(right);
vector<punct> by_y;
merge(begin(rez_left.by_y), end(rez_left.by_y), begin(rez_right.by_y), end(rez_right.by_y), back_inserter(by_y),
cmp_by_y);
vector<punct> fasie;
double rez = min(rez_left.dist, rez_right.dist);
copy_if(begin(by_y), end(by_y), back_inserter(fasie), [mid, rez](const punct& p1){
return mid-rez <= p1.x && p1.x <= mid+rez; });
for(int i = 0; i < fasie.size(); ++i){
for(int j = i-1; j >= 0 && abs(fasie[i].y-fasie[j].y) <= rez; --j){
rez = min(rez, dist(fasie[i], fasie[j])); } }
return cmap_rez_t { move(by_y), rez }; }
int main(){
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
f >> n;
vector<punct> v(n);
for(auto& p : v){
f >> p.x >> p.y; }
g << fixed << setprecision(6) << cmap(v).dist << endl;
return 0; }