Cod sursa(job #1025822)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 10 noiembrie 2013 16:31:55
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100010
using namespace std;

struct Punct {
  int x, y;
}v[NMAX];
int N;

inline bool compareAbscissa(const Punct &p1, const Punct &p2) {
  return p1.x < p2.x;
}

inline bool compareOrdinate(const Punct &p1, const Punct &p2) {
  return p1.y < p2.y;
}

void input() {
  freopen("cmap.in", "r", stdin);
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%d %d", &(v[i].x), &(v[i].y));
  }
}

double distance(const Punct &p1, const Punct &p2) {
  return sqrt(1.0*(p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

double dividescu(const int &left, const int &right) {
  if (right - left <= 2) {
    double d = 4000000000.0;

    for (int i = left; i < right; ++i) {
      for (int j = i + 1; j <= right; ++j) {
        double dist = distance(v[i], v[j]);
        d = min(dist, d);
      }
    }

    //mini-sortare dupa ordonache:
    sort(v + left, v + right + 1, compareOrdinate);
    return d;
  }

  const int mid = left + (right - left) / 2;
  double d = min(dividescu(left, mid), dividescu(mid + 1, right));

  //intercla$are
  vector<Punct> temp;
  int i = left, j = mid + 1;
  while (i <= mid && j <= right) {
    if (compareOrdinate(v[i], v[j])) {
      temp.push_back(v[i]);
      ++i;
    } else {
      temp.push_back(v[j]);
      ++j;
    }
  }

  while (i <= mid) {
    temp.push_back(v[i]);
    ++i;
  }
  while (j <= right) {
    temp.push_back(v[j]);
    ++j;
  }

  int size = right - left + 1;
  for (i = 0; i < size; ++i) {
    v[i + left] = temp[i];
  }

  //acum ca le-am interclasat, sa vedem distanta...
  for (i = left; i < right; ++i) {
    int stop = min(i + 7, right);
    for (j = i + 1; j <= stop; ++j) {
      d = min(d, distance(v[i], v[j]));
    }
  }

  return d;
}

void solve() {
  sort(v, v + N, compareAbscissa);
  double d = dividescu(0, N - 1);

  freopen("cmap.out", "w", stdout);
  printf("%0.6f", d);
}

int main() {
  input();
  solve();

  return 0;
}