Soluzione esercizio 2

Anche se non specificato nel testo, ma come spiegato durante il compito, per rettangolo con diagonale (A,B)-(C,D) si intende il rettangolo cone lati paralleli agli assi cartesiani e con angolo inferiore sinistro il punto (A,B) e con angolo superiore destro il punto (C,D).

Per risolvere questo esercizio si può utilizzare il seguente algoritmo:

1. definire la generatrice di numeri casuali (facoltativo);
2. determinare qual è il lato più corto e prendere come raggio R un centesimo di tale valore;
3. perché le circonferenze siano completamente contenute nel rettangolo con diagonale (A,B)-(C,D), i loro centri devono trovarsi all'interno del rettangolo di diagonale (A+R,B+R)-(C-R,D-R);
4. generiamo 500 punti all'interno di tale rettangolo;
5. misuriamo la distanza di ogni punto con tutti gli altri;
6. se il punto ha distanza maggiore di 2R da tutti gli altri, allora la circonferenza corrispondente non ne interseca nessun altra e si può incrementare il contatore di circonferenze buone;
7. alla fine si stampa il valore del contatore.

Il programma

Questo è un programma funzionante che realizza l'algoritmo sopra descritto:

#include <stdlib.h>
#include <math.h>

#define N 500

/* 
   Definizione di rndm(), che restituisce un numero casuale
   uniformemente distribuito tra 0 ed 1.
*/
double rndm() {
  return (double)rand()/(double)RAND_MAX;
}

int main() {
  /* Dichiarazione delle variabili, 
     i valori di A, B, C, D sono solo esemplificativi. */
  double A=0, B=0., C=10., D=5.;
  double raggio, xmin, xmax, ymin, ymax, dist;
  double x[N], y[N];
  int i, j, contatore=0;
  /* Inizializzazione della zona in cui devono essere contenuti 
     i centri delle circonferenze.                              */
  if ( (C-A) > (D-B) ) raggio=(D-B)/100.;
  else raggio=(C-A)/100.;
  xmin = A+raggio;
  xmax = C-raggio;
  ymin = B+raggio;
  ymax = D-raggio;
  /* Generazione dei centri delle circonferenze. */
  for ( i=0; i<N; i++) {
    x[i] = xmin+rndm()*(xmax-xmin);
    y[i] = ymin+rndm()*(ymax-ymin);
  }
  /* per ogni circonferenza si controlla se questa non ne interseca 
     nessun altra. Se una circonferenza non ha intersezioni, alla fine 
     del ciclo interno j vale N.
  */
  for ( i=0; i<N; i++) {
    for (j=0; j<N; j++) {
      if (j!=i) {
	dist = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
	if ( dist < 2.*raggio ) break;
      }
    }
    if (j==N) contatore++;
  }
  /* Stampa il risultato ed esce dal programma. */
  printf("Trovate %d circonferenze che non si intersecato.\n",contatore);
  return 0;
}

Variazioni

Siccome sono metodi molto diffusi di fare la stessa cosa, ecco alcune possibili alternative al codice appena presentato.

Per i virtuosi del C le istruzioni:

  if ( (C-A) > (D-B) ) raggio=(D-B)/100.;
  else raggio=(C-A)/100.;

   raggio = ( (C-A)>(D-B)?(D-B):(C-A) )/100.;

Invece di fare il break del ciclo su j, si può memorizzare in una variabile temporanea la minima distanza della circonferenza in questione tra tutte le altre e confrontarla con 2R alla fine del ciclo:

    distmin = 100.*raggio;
    for (j=0; j<N; j++) {
      if (j!=i) {
	dist = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
	if ( dist < distmin ) distmin=dist;
      }
    }
    if (distmin>2.*raggio) contatore++;