2-D плоскостное подразделение

Question

В этом случае:

* Шеф-повар работает с линиями на двумерном плоскости. Он знает, что каждая линия на плоскости может быть четко определена тремя коэффициентами A, B и C: любая точка (x, y) лежит на прямой тогда и только тогда, когда A * x + B * y + C = 0. Назовем набор линий должен быть совершенным, если не существует точки, принадлежащей двум или более различным линиям множества. У него есть набор линий на плоскости, и он хочет узнать размер самого большого совершенного подмножества этого множества.

Входной

Первая строка входных данных содержит один целые числа 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 * х + 4 * у + 5 = 0 и 30 * х + 40 * у + 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.