Soluzione esercizio 2

Anche se non specificato nel testo, ma come spiegato durante il compito, la lettera O è di norma utilizzata per indicare il l'origine degli assi cartesiani, ovvero il punto (0,0).

Il tipo di problema è molto simile a quello del compito precedente e si può risolvere con un algortimo simile. Tuttavia, per variare un po', stavolta lo risolveremo usando un algoritmo un attimo più complesso, che utilizza un vettore temporaneo per memorizzare il fatto che una circonferenza ne interseca delle altre o meno.

Il vantaggio di tale algoritmo è che non dobbiamo fare N(N-1) confronti, a se già troviamo che una circonferenza ne interseca un'altra, non ci preoccupiamo di confrontarla con tutte le altre. Chiaramente questo va a scapito di un maggiore utilizzo della memoria.

Procederemo dunque come segue:

definire la generatrice di numeri casuali (facoltativo);
perché le circonferenze siano completamente contenute nel cerchio, il loro centro deve avere una distanza dall'origine compresa tra 0 e 0.99r;
generiamo 500 punti in coordinate polari, con il raggio compreso tra questi limiti e l'angolo azimutale compreso tra 0 e 2π: la distribuzione dei punti non sarà uniforme nel piano, ma più densa attorno all'origine degli assi, tuttavia il testo dell'esercizio non richiede l'uniformità dei punti;
convertiamo immediatamente i punti in coordinate cartesiane, dove è più semplice calcolare la distanza;
iniziamo un ciclo su tutti i punti;
se si sa già che il punto dato interseca un'altra circonferenza, si passa direttamente a quello successivo;
altrimenti misuriamo la distanza del punto con tutti gli altri;
la distanza tra due punti è minore della somma dei raggi delle due circonferenze, allora queste si intersecano: in questo caso imagazziniamo in un vettore ausiliario questa informazione;
se invece la circonferenza che stiamo considerando non ne interseca nessun altra, si incrementa il contatore di circonferenze buone;
alla fine si stampa il valore del contatore.

Il programma

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

#include <math.h>
#include <stdlib.h>
#include <stdio.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,
     il valore di R è solo esemplificativo. */
  double R=1000.;
  double rmax, dist, raggio, erre, phi;
  double x[N], y[N];
  int intersec[N];
  int i, j, contatore=0;

  /* Inizializzazione della zona in cui devono essere contenuti
     i centri delle circonferenze.                              */
  raggio = R/100.;
  rmax   = R-raggio;
  /* Generazione dei centri delle circonferenze.
     M_PI è il valore di pi greco definito in math.h            */
  for ( i=0; i<N; i++) {
    erre = rndm()*rmax;
    phi  = rndm()*2.*M_PI;
    x[i] = erre*cos(phi);
    y[i] = erre*sin(phi);
    /* ne approfittiamo per azzerare il marchiatore delle circonferenze
       che si intersecano.                                              */
    intersec[i] = 0;
  }
  /*
     Per ogni circonferenza si controlla se questa non ne interseca
     nessun altra.
  */
  for ( i=0; i<N; i++) {
    /* se sappiamo già che questa circonferenza ha un'intersezione
       possiamo passare direttamente alla prossima                 */
    if (intersec[i]!=0) continue;
    for (j=0; j<N; j++) {
      if (j==i) continue;
      dist = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
      if ( dist < 2.*raggio ) {
        intersec[i]=intersec[j]=1;
       break;
      }
    }
    /* se non ci sono intersezioni, allora si incrementa il contatore. */
    if ( intersec[i]==0 ) contatore++;
  }
  /* Stampa il risultato ed esce dal programma. */
  printf("Trovate %d circonferenze che non si intersecano.\n",contatore);
  return 0;
}