Cod sursa(job #1333619)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 3 februarie 2015 13:51:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;

struct point {
   int x, y;
};

int N;
point Px[MAXN];
point Py[MAXN];
vector<point> S;

bool cmp1(point a, point b) {
   if(a.x == b.x)
      return a.y < b.y;
   return a.x < b.x;
}

bool cmp2(point a, point b) {
   if(a.y == b.y)
      return a.x < b.x;
   return a.y < b.y;
}

double dist(point a, point b) {
   return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double split(int st, int dr, double d) {
   int med = (st + dr) / 2, xm = Px[med].x;
   double dmin = d;
   for(int i = 1; i <= N; ++i) {
      if(Py[i].x >= xm - d && Py[i].x <= xm + d) {
         S.push_back(Py[i]);
      }
   }
   for(int i = 0; i < S.size() - 1; ++i) {
      for(int j = 1; j < 7 && i + j < S.size(); ++j) {
         double dc = dist(S[i], S[i + j]);
         if(dc < dmin)
            dmin = dc;
      }
   }
   return dmin;
}

double solve(int st, int dr) {
   if(dr - st == 2) {
      return min(min(dist(Px[st], Px[st + 1]), dist(Px[st], Px[dr])), dist(Px[st + 1], Px[dr]));
   }
   if(dr - st == 1) {
      return dist(Px[st], Py[dr]);
   }
   double d1 = solve(st, (st + dr) / 2);
   double d2 = solve((st + dr) / 2 + 1, dr);
   double d3 = split(st, dr, min(d1, d2));
   return d3;
}

int main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");
    cin >> N;
    for(int i = 1; i <= N; ++ i) {
      cin >> Px[i].x >> Px[i].y;
      Py[i].x = Px[i].x;
      Py[i].y = Px[i].y;
    }
    sort(Px + 1, Px + N + 1, cmp1);
    sort(Py + 1, Py + N + 1, cmp2);
    cout << fixed << setprecision(6) << solve(1, N) << '\n';
    return 0;
}