Division de plan 2-D

Question

Voici l'énoncé du problème:

* Chef travaille avec des lignes sur un plan 2D. Il sait que chaque ligne d'un plan peut être clairement définie par trois coefficients A, B et C: tout point (x, y) se trouve sur la ligne si et seulement si A * x + B * y + C = 0. Appelons un ensemble de lignes pour être parfait s'il n'existe pas un point appartenant à deux ou plusieurs lignes distinctes de l'ensemble. Il a un ensemble de lignes sur un avion et il veut trouver la taille du plus grand sous-ensemble parfait de cet ensemble.

entrée

La première ligne d'entrée contient un des nombres entiers T désignant le nombre de cas de test. Chaque cas de test est constitué d'un entier N indiquant le nombre de lignes. Les N lignes suivantes contiennent 3 entiers séparés par des espaces, chacun désignant respectivement les coefficients A, B et C.

Sortie

Pour chaque sortie de cas de test la cardinalité du plus grand sous-ensemble parfait en une seule ligne. l'entrée de contraintes:

1 5 
1 1 0 
1 2 3 
3 4 5 
30 40 0 
30 40 50 

sortie:. 2 Explication Lignes 3 * x + 4 * y + 5 = 0 et 30 * x + 40 * y + 0 = 0, forment un plus grand sous-ensemble parfait *

Donc, si les rapports de As et Bs sont les mêmes, alors les lignes seraient parallèles ce qui satisfait l'énoncé du problème. Par exemple: si A [1]/B [1] == A [2]/B [2] alors ces lignes 1 et 2 sont parallèles. Mais quand les deux lignes en question sont les mêmes lignes, ce qui signifie qu'il y a un nombre infini de points communs, cette équation est vraie, ce qui n'est pas ce que veut le problème. Nous devons donc utiliser C pour déterminer si les lignes sont identiques ou non (c'est-à-dire A [1]/A [2] == B [1]/B [2] == C [1]/C [2]) . Mais le code que j'ai écrit avec ces idées est si inefficace. Pouvez-vous tous suggérer une solution plus rapide?

Answer 1

Vous pouvez écrire un algorithme linéaire pour cela.

L'idée est d'avoir une carte, où la clé est une direction et la valeur est un ensemble. Pour chaque direction, l'ensemble ne contient que des lignes différentes ayant la direction donnée. Ensuite, la réponse est la taille du plus grand ensemble. La direction d'une ligne Ax + By + C = 0 est A/B. Le problème est que si B=0 il ne fonctionnera pas tout à fait comme une clé. Vous pouvez avoir un jeu spécial pour le cas B=0, que vous gardez séparé et que vous n'insérez pas dans la carte. Les valeurs que vous insérez dans l'ensemble pour une ligne donnée Ax + By + C = 0 doivent être C/B. Dans le cas particulier, lorsque B = 0, vous devez utiliser C/A.