Cod sursa(job #1657781)

Utilizator hrazvanHarsan Razvan hrazvan Data 20 martie 2016 19:56:08
Problema Cele mai apropiate puncte din plan Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 2.5 kb
#include <stdio.h>
#include <math.h>
#define MAXN 100000
#define INF 9000000000.0
int x[MAXN], y[MAXN];
int dx[MAXN], dy[MAXN];
double dd = INF;

inline int myabs(int a){
  return a < 0 ? -a : a;
}

inline double dist(int *x, int *y, int i, int j){
  return sqrt(1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]));
}

void qs(int st, int dr){
  int i = st, j = dr, piv = x[(st + dr) / 2], aux;
  while(i <= j){
    while(x[i] < piv)
      i++;
    while(x[j] > piv)
      j--;
    if(i <= j){
      aux = x[i];  x[i] = x[j];  x[j] = aux;
      aux = y[i];  y[i] = y[j];  y[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

inline void merge(int p1, int p2, int p3){
  int a = p1, b = p2 + 1, vx[MAXN], vy[MAXN], dv = 0, i;
  while(a <= p2 || b <= p3){
    if(a > p2 || (a <= p2 && b <= p3 && y[a] >= y[b])){
      vx[dv] = x[b];
      vy[dv] = y[b];
      dv++;
      b++;
    }
    else  if(b > p3 || (b <= p3 && a <= p2 && y[b] >= y[a])){
      vx[dv] = x[a];
      vy[dv] = y[a];
      dv++;
      a++;
    }
  }
  for(i = 0; i < dv; i++){
    x[p1 + i] = vx[i];
    y[p1 + i] = vy[i];
  }
}

void gasesc(int st, int dr){
  int i, j, min, p, aux, drd;
  double d;
  if(dr - st + 1 <= 3){
    for(i = st; i <= dr; i++){
      for(j = i + 1; j <= dr; j++){
        d = dist(x, y, i, j);
        if(d < dd)
          dd = d;
      }
    }
    for(i = st; i < dr; i++){
      min = y[i];
      p = i;
      for(j = i + 1; j <= dr; j++){
        if(min > y[j]){
          min = y[j];
          p = j;
        }
      }
      aux = x[i];  x[i] = x[p];  x[p] = aux;
      aux = y[i];  y[i] = y[p];  y[p] = aux;
    }
  }
  else{
    int m = (st + dr) / 2, cx, cy;
    cx = x[m];  cy = y[m];
    gasesc(st, m);
    gasesc(m + 1, dr);
    merge(st, m, dr);
    drd = 0;
    for(i = st; i <= dr; i++){
      if(myabs(x[i] - cx) <= dd){
        dx[drd] = x[i];
        dy[drd] = y[i];
        drd++;
      }
    }
    for(i = 0; i < drd; i++){
      for(j = i + 1; j < drd && j < i + 8; j++){
        d = dist(dx, dy, i, j);
        if(d < dd)
          dd = d;
      }
    }
  }
}

int main(){
  FILE *in = fopen("cmap.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++)
    fscanf(in, "%d%d", &x[i], &y[i]);
  fclose(in);
  qs(0, n - 1);
  gasesc(0, n - 1);
  FILE *out = fopen("cmap.out", "w");
  fprintf(out, "%lf", dd);
  fclose(out);
  return 0;
}