Cod sursa(job #2803311)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 19 noiembrie 2021 19:52:01
Problema Cele mai apropiate puncte din plan Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 3.63 kb
#include <stdio.h>
#include <ctype.h>
#include <math.h>

// Program de Mircea Rebengiuc
// inceput pe 2021.11.19

// facut din ce imi mai aduc aminte din clasa 7

#define MAXN 100000
#define INF 2000000000.0

int x[MAXN];
int y[MAXN];

// vectori de puncte auxiliari pentru
// selectarea punctelor interesante
// si pentru mergesort
int auxx[MAXN];
int auxy[MAXN];

static inline double getDist( int x1, int x2, int y1, int y2 ){
  return sqrt(
    ((long long)(x1 - x2)) * (x1 - x2) + 
    ((long long)(y1 - y2)) * (y1 - y2)
  );
}

static inline double mind( double a, double b ){
  return a < b ? a : b;
}

void myqsort( int begin, int end ){
  int b = begin - 1, e = end + 1, p = x[(begin + end) / 2], aux;

  while( x[++b] < p );
  while( x[--e] > p );

  while( b < e ){
    aux = x[b];
    x[b] = x[e];
    x[e] = aux;

    aux = y[b];
    y[b] = y[e];
    y[e] = aux;
    
    while( x[++b] < p );
    while( x[--e] > p );
  }

  if( begin < e )
    myqsort(begin, e);
  if( e + 1 < end )
    myqsort(e + 1, end);
}

double minDist( int st, int dr ){
  int mij = (st + dr) / 2, i, j1, j2, j, split;
  int auxmij, auxn;
  double min_st_dr, retval;

  if( st == dr )
    return INF;
  
  if( st + 1 == dr )// daca fac toata chestia doar pentru 2 puncte irosesc timpul
    return getDist(x[st], x[dr], y[st], y[dr]);

  // la inceput [st, dr] este sortat dupa x
  split = x[mij];
  retval = min_st_dr = mind(minDist(st, mij), minDist(mij + 1, dr));
  // acum [st, mij] si [mij + 1, dr] sunt sortate dupa y, nu dupa x

  // luam numai punctele la distanta mai mica decat min_st_dr de split pentru ca daca sunt mai departate
  // inseamna ca nu au cum sa aiba o distanta mai mica decat cea curenta cu un punct din partea opusa
  j = 0;// indicile curent in auxx[] si auxy[]
  for( i = st ; i <= mij ; i++ )
    if( split - x[i] < min_st_dr ){
      auxx[j] = x[i];
      auxy[j] = y[i];
      j++;
    }
  auxmij = j;
  for( i = mij + 1 ; i <= dr ; i++ )
    if( x[i] - split < min_st_dr ){
      auxx[j] = x[i];
      auxy[j] = y[i];
      j++;
    }
  auxn = j;

  // tinem intervalul [j1, j2] de puncte din partea dreapta care sunt la distanta <= min_st_dr pe y fata de i
  // pot fi maxim 6 puncte in intervalul [j1, j2] pentru ca distanta minima dintre doua puncte din partea
  // dreapta este >= min_st_dr inseamna ca 
  j1 = j2 = auxmij;

  for( i = 0 ; i < auxmij ; i++ ){
    while( j1 < auxn && auxy[j1] + min_st_dr < auxy[i] )// j1 is inclusive
      j1++;
    while( j2 < auxn && auxy[j2] - min_st_dr <= auxy[i] )// j2 is exclusive
      j2++;

    for( j = j1 ; j < j2 ; j++ )
      retval = mind(retval, getDist(auxx[i], auxx[j], auxy[i], auxy[j]));
  }

  // tot ce mai trebuie sa facem e sa dam merge la cele doua jumatati
  for( i = st ; i <= dr ; i++ ){
    auxx[i] = x[i];
    auxy[i] = y[i];
  }

  i = st;
  j = dr;
  j1 = st;// j1 is the output index
  while( i <= mij && j <= dr ){
    if( auxy[i] < auxy[j] ){
      x[j1] = auxx[i];
      y[j1++] = auxy[i++];
    }else{
      x[j1] = auxx[j];
      y[j1++] = auxy[j++];
    }
  }

  while( i <= mij ){
    x[j1] = auxx[i];
    y[j1++] = auxy[i++];
  }

  while( j <= dr ){
    x[j1] = auxx[j];
    y[j1++] = auxy[j++];
  }

  return retval;
}

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch;

  while( !isdigit(ch = fgetc(fin)) );
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n;
}

int main(){
  fin  = fopen("cmap.in",  "r");
  fout = fopen("cmap.out", "w");

  int n, i;

  n = fgetint();
  for( i = 0 ; i < n ; i++ ){
    x[i] = fgetint();
    y[i] = fgetint();
  }

  myqsort(0, n - 1);

  fprintf(fout, "%lf\n", minDist(0, n - 1));

  fclose(fin);
  fclose(fout);
  return 0;
}