Cod sursa(job #1546752)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 8 decembrie 2015 17:51:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 3.81 kb
// Metoda:
// Sorteaza punctele dupa abscisa
// Imparte planul dupa o linie verticala
// Rezolva recursiv pentru punctele din stanga, respectiv dreapta liniei
// Afla distanta minima intre un punct care se afla in stanga liniei si un punct care se afla in dreapta sa
// Rezultatul final este minimul dintre aceste trei valori
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

#define MAX_N 100000
#define INF 800000000000000000LL
#define MAX_PICK 6
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define MAX(A, B) ((A) > (B) ? (A) : (B))

typedef struct {
  int x, y;
} point;

point v[MAX_N];        // punctele date
point tmpMerge[MAX_N]; // vector de manevra, pentru interclasare

// sorteaza crescator dupa abscisa
void myqsort( int begin, int end ) {
  int b = begin, e = end;
  int pivot = v[rand() % (end - begin + 1) + begin].x;
  point aux;

  while ( b <= e ) {
    while ( v[b].x < pivot ) b++;
    while ( v[e].x > pivot ) e--;
    if ( b <= e ) {
      aux = v[b]; v[b] = v[e]; v[e] = aux;
      b++; e--;
    }
  }
  if ( begin < e ) myqsort( begin, e );
  if ( b < end ) myqsort( b, end );
}

long long pointDistance( point *A, point *B ) {
  return 1LL * ( A->x - B->x ) * ( A->x - B->x ) + 1LL * ( A->y - B->y ) * ( A->y - B->y );
}

long long cmap( int begin, int end ) {
  point aux;
  int i, j, k, med, medX;
  long long distB, distE, dist;

  if ( end - begin == 1 ) {        // 2 puncte
    if ( v[begin].y > v[end].y ) { // mentine sirul sortat dupa ordonata
      aux = v[begin]; v[begin] = v[end]; v[end] = aux;
    }
    return pointDistance( &v[begin], &v[end] );
  } else if ( end - begin > 1 ) {
    med = ( begin + end ) / 2; // imparte la mijloc
    medX = v[med].x;           // retine abscisa, ne vom raporta la aceasta cand selectam punctele pentru pasul final
    distB = cmap( begin, med ); distE = cmap( med + 1, end ); // calculeaza rezultatul recursiv pentru cele doua submultimi
    dist = MIN( distB, distE );                               // retine in dist rezultatul

    // interclaseaza sirurile dupa ordonata
    i = begin; j = med + 1; k = begin;
    while ( i <= med && j <= end ) {
      if ( v[i].y < v[j].y ) {
        tmpMerge[k] = v[i];
        i++;
      } else {
        tmpMerge[k] = v[j];
        j++;
      }
      k++;
    }
    while ( i <= med ) tmpMerge[k++] = v[i++];
    while ( j <= end ) tmpMerge[k++] = v[j++];

    // copiaza sirul in v
    for ( i = begin; i <= end; i++ )
      v[i] = tmpMerge[i];

    // doar punctele la o distanta mai mica decat dist fata de linia verticala pot duce la o solutie mai buna
    k = 0;
    for ( i = begin; i <= end; i++ ) {
      if ( abs( v[i].x - medX ) <= dist ) {
        tmpMerge[k++] = v[i];
      }
    }
    // pentru fiecare punct p din stanga liniei verticale trebuie sa comparam distanta cu
    // punctele care se afla in dreptunghiuri de marime (dist, dist * 2) din dreapta liniei
    // un dreptunghi de lungime dist si latime 2 * dist poate contine maxim 6 puncte,
    // astfel incat distante dintre oricare 2 puncte este cel putin dist: http://www.cs.mcgill.ca/~cs251/ClosestPair/proofbox.html
    for ( i = 1; i < k; i++ ) {
      med = MAX( 0, i - MAX_PICK );
      for ( j = i - 1; j >= med; j-- ) {
        distB = pointDistance( &tmpMerge[i], &tmpMerge[j] );
        if ( distB < dist ) {
          dist = distB;
        }
      }
    }
    return dist;
  }
  return INF;
}

int main( void ) {
  FILE *fin, *fout;
  int n, i;

  fin = fopen( "cmap.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d%d", &v[i].x, &v[i].y );
  }
  fclose( fin );

  myqsort( 0, n - 1 );

  fout = fopen( "cmap.out", "w" );
  fprintf( fout, "%.6f\n", sqrt( cmap( 0, n - 1 ) ) );
  fclose( fout );
  return 0;
}