Cod sursa(job #589146)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 11 mai 2011 09:47:47
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <cstdio>
#include <utility>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct pct {
  int x, y;
};

const int N = 100005;

int n;

pct sorted_x[N], sorted_y[N];

void read() {
  scanf("%d", &n);

  for(int i = 1; i <= n; ++ i)
    scanf("%d%d", &sorted_x[i].x, &sorted_x[i].y);
}

const double INF = 1 << 30;

inline double min(double x, double y) {
  return x < y ? x : y;
}

inline double dist(pct x, pct y) {
  return sqrt((double)(x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}

bool comp(const pct &A, const pct &B) {
  if (A.x < B.x)
    return 1;

  if (A.x > B.x)
    return 0;

  return A.y < B. y;
}

void init() {
  sort(sorted_x + 1, sorted_x + n + 1, comp);

  for (int i = 1; i <= n; ++ i)
    sorted_y[i] = sorted_x[i];
}

double solve(int st, int dr) {
  if (st == dr)
    return INF;
  
  if (st + 1 == dr) {
    if (sorted_y[st].y > sorted_y[st + 1].y)
      swap(sorted_y[st], sorted_y[st + 1]);

    return dist(sorted_x[st], sorted_x[st + 1]);
  }

  int mid = (st + dr) / 2;

  double best = min(solve(st, mid), solve(mid + 1, dr));

  vector <pct> aux_y;

  for (int i = st, j = mid + 1; i <= mid || j <= dr;) {
    if (i > mid) {
      aux_y.push_back(sorted_y[j]);
      ++ j;
      continue;
    }
    
    if (j > dr) {
      aux_y.push_back(sorted_y[i]);
      ++ i;
      continue;
    }

    if (sorted_y[i].y > sorted_y[j].y) {
      aux_y.push_back(sorted_y[j]);
      ++ j;
      continue;
    }

    aux_y.push_back(sorted_y[i]);
    ++ i;
    continue;
  }

  for (int i = 0; i < aux_y.size(); ++ i)
    sorted_y[st + i] = aux_y[i];

  aux_y.clear();

  for (int i = st; i <= dr; ++ i)
    if (sorted_y[i].x >= sorted_x[mid].x - best && sorted_y[i].x <= sorted_x[mid].x + best)
      aux_y.push_back(sorted_y[i]);

  for (int i = 0; i < aux_y.size(); ++ i)
    for (int j = i + 1; j < aux_y.size() && j - i <= 8; ++ j)
      if (dist(aux_y[i], aux_y[j]) < best)
        best = dist(aux_y[i], aux_y[j]);

  return best;
}

int main() {
  freopen("cmap.in", "r", stdin);
  freopen("cmap.out", "w", stdout);

  read();

  init();

  printf("%lf\n", solve(1, n));

  return 0;
}