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 (x, y) è 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
con
Le intersezioni tra la retta e una circonferenza con centro nell’origine
con
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; }