Cod sursa(job #2917321)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 4 august 2022 13:36:21
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.82 kb
// Program de Mircea Rebengiuc
// inceput pe 2021.11.19
// reluat pe 2022.08.04
 
// facut din ce imi mai aduc aminte din clasa 7

#include <stdio.h>
#include <ctype.h>
#include <math.h>

#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 long double getDist( int x1, int x2, int y1, int y2 ){
  return sqrtl(
    ((long long)(x1 - x2)) * (x1 - x2) + 
    ((long long)(y1 - y2)) * (y1 - y2)
  );
}
 
static inline long double mind( long double a, long 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 );
}
 
long double minDist( int st, int dr ){
  int mij = (st + dr) / 2, i, j1, j2, j, split;
  int auxmij, auxn;
  long 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 = mij+1;
  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, semn = 1;
 
  while( isspace( ch = fgetc( fin ) ) );
  if( ch == '-' ){
    semn = -1;
    ch = fgetc( fin );
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( fin ) ) );
 
  return n * semn;
}
 
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;
}