二維平面劃分

Question

以下是問題陳述：

*廚師正在使用二維平面上的線。他知道一個平面上的每一條線都可以用三個係數A，B和C來明確定義：當且僅當A * x + B * y + C = 0時，任何點（x，y）都位於該線上。讓我們調用如果不存在屬於該組的兩條或更多不同線的點，則一組線將是完美的。他在飛機上有一系列的線條，他想要找出這個集合中最大的完美子集的大小。

輸入

輸入的第一行包含一個整數T代表的測試用例的數量。每個測試用例由一個整數N表示行數。接下來的N行包含3個空格分隔的整數，每個整數分別表示係數A，B和C.

輸出

對於每組數據輸出最大完美子集的在一行中的基數。約束 輸入：

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

輸出：2說明 線3 * X + 4 * Y + 5 = 0至30 * X + 40 * Y + 0 = 0形式的最大完美子集*

因此，如果As和Bs的比率相同，那麼這些線將是平行的，從而完成問題陳述。例如：如果A [1]/B [1] == A [2]/B [2]，那麼這些第一行和第二行是平行的。但是，當這兩條線是相同的線，這意味着有無限的共同點，這個等式成立，這不是問題所需。所以我們需要用C來確定這些行是否相同（即A [1]/A [2] == B [1]/B [2] == C [1]/C [2]） 。但是我用這些想法寫的代碼效率很低。你們能否提出一個更具時效性的解決方案？

Answer 1

你可以爲此寫一個線性算法。

這個想法是有一個地圖，其中的關鍵是一個方向，值是一個集合。 對於每個方向，該集合只包含具有給定方向的不同線條。那麼答案就是大集合的大小。

線的方向Ax + By + C = 0是A/B。問題是，如果B=0它不會作爲一個關鍵工作。 您可以爲案件B=0設置專門的設置，您可以將其單獨保存並不要插入地圖。

您爲給定行Ax + By + C = 0插入集合的值應爲C/B。 在特殊情況下，當B = 0時，應該使用C/A。