Segmento e infinite circonferenze

Correttore online – Intermedi

In un piano cartesiano è disegnato un insieme infinito di circonferenze concentriche, ossia aventi centro comune, definite come segue: il loro centro è situato nell’origine degli assi cartesiani e i loro raggi sono tutti gli interi positivi (r = 1, 2, 3, …).

Nello stesso piano è tracciato il segmento S di estremi (x1, y1) e (x2, y2).
Diciamo che (xy) è un punto d’intersezione se appartiene sia a S che a una delle circonferenze.
La prima condizione viene soddisfatta se e solo se vale

(y-y1)(x2-x1)=(x-x1)(y2-y1)

con

min(x1, x2) ≤ x ≤ max(x1, x2)
min(y1, y2) ≤ y ≤ max(y1, y2).

La seconda condizione viene soddisfatta se e solo se x2+y2=r2, dove r è un intero positivo (il raggio di una delle circonferenze).
Un eventuale punto di tangenza fra S e una circonferenza viene considerato punto di intersezione.

Scrivere un programma che calcola il numero di punti di intersezione fra il segmento S e le circonferenze nell’insieme dato.

Suggerimento

I possibili valori utili di r sono finiti.
Impostare il sistema di equazioni e, con il metodo di sostituzione, ottenere un’equazione di secondo grado per ciascun valore r, tenendo presente i vincoli sopra.

Dati di input

Il file input.txt è composto da un’unica riga contenente i quattro interi x1, y1, x2 e y2 (1 ≤ x1, y1, x2, y2 ≤ 100) separati da uno spazio, tali che il segmento così identificato ha lunghezza non nulla.

Dati di output

Il file output.txt è composto da una sola riga contenente un intero non negativo, ossia il numero di intersezioni tra il segmento indicato nell’input e le circonferenze appartenenti all’insieme infinito.

Esempi di input/output

input.txt output.txt
1 1 2 1 1
1 2 2 1
0

Considera la retta passante per 2 punti

segmento_html_5406d6b5

con

segmento_html_57e7c764

Le intersezioni tra la retta e una circonferenza con centro nell’origine

segmento_html_m6fdd555

segmento_html_m13fd260c

segmento_html_m6dfbbb9c

segmento_html_m2b0b06ca

con

segmento_html_2f57195f

Dal segno del discriminante si deduce il numero di intersezioni tra la retta e la circonferenza.
Se si ripete il calcolo per ognuna delle circonferenze…
Osserva che a e b dipendono soltanto dalla retta.


/*
   www.valcon.it
   Esercizi preparatori - Intermedi - Segmento
   
   Se la retta per i due punti è verticale (m infinito...)
   			uso il trucchetto delle distanze
   altrimenti
   			seguo il metodo analitico
			per le circonferenze interessate...
*/

#include
#include
#include

using namespace std;

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	double   x1, y1, x2, y2,		// double per non fallire le divisioni...
	         xmin, ymin, xmax, ymax,// intervalli accettabili	         
	         d1, d2, rmin, rmax,    // distanze e raggi accettabili
	         m, q,					// la retta passante per i 2 punti
			 r, 					// per ogni circonferenza
			 a, b, c,	 			// equazione di 2° grado risolvente
			 delta,                 // discriminante
			 xi, yi;				// punto di intersezione
	int      contatore=0;	        // risultato
	
	fin >> x1 >> y1 >> x2 >> y2;	
	
	if (x1 == x2)					// scorciatoia
		contatore=abs(y1-y2);		// se la retta è verticale
	else
	{			
		m=(y2-y1)/(x2-x1);			// parametri retta
		q=-m*x1+y1;					
		a=1+m*m;					// parametri risolvente
		b=2*m*q;					// c dopo perché dipende da r...
	
		rmin=abs(q)/sqrt(1+m*m);	// distanza della retta dall'origine
		rmin=ceil(rmin);			// per la prima circonferenza utile
		d1=sqrt(x1*x1+y1*y1);	   	//
		d2=sqrt(x2*x2+y2*y2);		//
		rmax=(d1 >= d2) ? d1 : d2;	//
		rmax=floor(rmax);			// e l'ultima circonferenza
		
		xmin=(x1 <= x2) ? x1 : x2;		
		xmax=(x1 >= x2) ? x1 : x2;
		ymin=(y1 <= y2) ? y1 : y2;
		ymax=(y1 >= y2) ? y1 : y2;			
	
		for(r=rmin; r <= rmax; r++)		// tutte le circonferenze tra...
		{	
			c=q*q-r*r;		
			delta=b*b-4*a*c;			// discussione...	
			if(delta >  0) 
			{
				delta=sqrt(delta);			
				xi=(-b-delta)/(2*a); 
				yi=m*xi+q; 
				if(xi >= xmin && xi <= xmax) 
					contatore++;							
				xi=(-b+delta)/(2*a); 
				yi=m*xi+q; 
				if(xi >= xmin && xi <= xmax) 
					contatore++;
	    	}
			else if(delta == 0) 
			{
				xi=-b/(2*a); 		 
				yi=m*xi+q;	
				if(xi >= xmin && xi <= xmax) 
					contatore++;
	    	}
		}		
	}
	fout << contatore;
}

Lascia un commento