Astrologia P49956

Les notes de l’últim examen preparat pel professor Oak van ser lamentables. Desesperat per trobar una explicació lògica al fenomen, el professor recorre a l’astrologia. Sabent la posició relativa de tots els estels respecte de la lluna durant la mitjanit del dia de l’examen, vol calcular quants parells d’estels estaven aliniats amb la lluna, per si aquest nombre tingués algun significat cabalístic.

Suposeu aquesta simplificació: La lluna i els estels són punts projectats en el cel, el qual considerem com un pla bidimensional. La lluna ocupa l’origen, i els estels ocupen diferents posicions (x, y), on x i y són enters. Cal calcular quants parells (x₁, y₁) i (x₂, y₂) són tals que la recta que els uneix passa per (0, 0).

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre d’estels n, seguit d’n parells diferents x y amb les coordenades dels estels. Podeu suposar 2 ≤ n ≤ 10⁴, que les coordenades es troben entre −10⁹ i 10⁹, i que cap estel es troba a l’origen.

Sortida

Per a cada cas, escriviu la quantitat de parells d’estels aliniats amb la lluna.

Pista

La solució esperada té cost inferior a Θ(n²).