Un file contiene le specifiche di un insieme di cerchi descritti nel piano cartesiano, un cerchio per riga. Ciascun cerchio è specificato da una stringa, che ne definisce il nome (max 127 caratteri senza spazi) e da 3 valori interi (x, y, r), dove (x, y) sono le coordinate del centro (interi con segno) e r è il raggio (intero maggiore di zero). I valori sono separati da spazi.

Per esempio:

C0 -1 -3 9
C1 0 0 10
C2 0 0 10
C3 -100 10 10
C4 -101 10 9
C5 1 1 1

Il nome del file viene passato al programma da linea di comando.

Definire una struttura dati struct cerchio al fine di rappresentare i dati letti da file.

Si stampi a video l'elenco dei cerchi nello stesso ordine con il quale sono stati letti da file. Si usi il seguente formato:

[CERCHI]
C0 -1 -3 9
C1 0 0 10
C2 0 0 10
C3 -100 10 10
C4 -101 10 9
C5 1 1 1

Definire una funzione carica_elenco come la seguente:

struct cerchio *carica_elenco(FILE *infile, int *n);

Riceve come parametro il nome del file contenente l'elenco dei cerchi e carica un array di strutture struct cerchio, allocato dinamicamente tramite malloc e realloc al suo interno. La funzione deve ritornare al programma chiamante il vettore così allocato e il numero di elementi caricati, quest'ultima cosa può essere fatta con il passaggio per riferimento di n.

Definire la funzione ordina che ordini i cerchi in ordine crescente di area. Si stampi a video l'elenco ordinato usando il formato:

[ORDINAMENTO]
C5 1 1 1
C0 -1 -3 9
C4 -101 10 9
C1 0 0 10
C2 0 0 10
C3 -100 10 10

Avendo caricato tutti i dati in memoria, è possibile utilizzare la qsort. L'unica cosa da definire è la funzione che confronta delle strutture struct cerchio sulla base della loro area. Per semplificare i calcoli (e renderli più veloci) si tenga presente che il confronto delle aree equivale al confronto dei raggi. In altre parole, il cerchio con il raggio maggiore è anche quello con l'area maggiore.

Alternativamente, si può implementare la propria funzione di ordinamento, per esempio utilizzando il metodo bubblesort.

Individuare le relazioni tra tutte le coppie di cerchi presenti nel file. Considerati due generici cerchi c1 e c2, le relazioni di interesse sono tre:

• c1 e c2 possono essere coincidenti
• c1 e c2 possono intersecarsi (si considera che non siano coincidenti)
• il cerchio c1 contiene il cerchio c2

Stampare a video i nomi delle coppie di cerchi che presentano una delle relazioni indicate, usando il seguente formato:

[RELAZIONI]
C0 INTERSECA C1
C0 INTERSECA C2
C0 CONTIENE C5
C1 INTERSECA C0
C1 COINCIDE C2
C1 CONTIENE C5
C2 INTERSECA C0
C2 COINCIDE C1
C2 CONTIENE C5
C3 INTERSECA C4
C4 INTERSECA C3

Definire la funzione relazione che, ricevendo come parametri due strutture di tipo struct cerchio, restituisca un codice che indica le seguenti relazioni tra coppie di cerchi: INTERSECA, CONTIENE, COINCIDE. Il "codice" che identifica la relazione può essere definito tramite delle #define (vedi S3.1 per una spiegazione di queste direttive del preprocessore).

Un esempio è il seguente:

#define NESSUNA    (0)
#define INTERSECA  (1)
#define CONTIENE   (2)
#define COINCIDE   (3)

int relazione(struct cerchio *c1, struct cerchio *c2);

Le relazioni tra i cerchi possono essere determinate semplicemente verificando delle relazioni sulla lunghezza dei raggi e le distanze tra i centri.

Disponendo della funzione relazione si può realizzare un ciclo for che itera su tutti i cerchi, con all'interno un altro ciclo for che confronta il cerchio di indice i con quello di indice j se i != j.

Si utilizzi il tool pvcheck di verifica automatica per testare il corretto funzionamento del programma (maggiori informazioni circa l'uso di pvcheck sono disponibili qui).

Il file contenente i test è cerchi.test. Per eseguire i test è necessario scaricare anche il seguente file di dati che è da salvare nella medesima directory del file di test:

• cerchi.txt

Il comando da eseguire per il test è il seguente:

pvcheck -f cerchi.test ./a.out

Il programma può anche essere verificato manualmente eseguendo:

./a.out cerchi.txt

Nella prossima pagina potrai esaminare un esempio di soluzione dell'esercizio.