То, что вы просите, может потребовать уточнения. Любые две точки коллинеарны друг другу, так как линия соединяет их. Чтобы сделать этот вопрос ответственным, мне кажется, что я должен истолковать то, что вы просите, иметь в виду следующее: если любое количество точек, больших или равных трем, все коллинеарно друг другу, наш набор неколлинеарных точек может содержать только одну коллинеарных точек.
Учитывая это, мы можем сделать следующее:
для каждой пары точек, вычислить наклон между ними как (y - y ') / (х - х '). Если x = x ', просто отметьте этот уклон как V.
рядом, для каждой пары точек и уклона проверьте все другие пары точек, включающие любую из точек в паре и посмотрите, совпадает ли соответствующий уклон с проверяемым. Возьмите все определенные таким образом точки и добавьте их в коллекцию и добавьте эту коллекцию в коллекцию.
По окончании вы получите коллекцию коллекций и все точки в каждая коллекция в вашей коллекции будет состоять из точек, которые все коллинеарны друг другу.
Теперь проблема заключается в следующем: найдите наибольшее количество точек, которые можно выбрать, чтобы не было двух очки существуют в двух коллекциях. Если бы вы выбрали две точки, которые были в одной из коллекций, вы бы выбрали две точки, которые были коллинеарны вместе, по крайней мере, с одной другой точкой.
На данный момент мы можем просто попробовать все 2 ^ n подмножеств из n точек и проверьте каждую из них, чтобы увидеть, является ли она приемлемой (в этом случае пересечение подмножества и любой коллекции имеет размер не более одного).
Пример:
p = (1, 1), q = (2, 2), r = (3, 3), s = (2, 3)
m = [ - 1 1 2]
[ 1 - 1 V]
[ 1 1 - 0]
[ 2 V 0 -]
(p, q): r yes, s no; collection (p, q, r)
(p, r): q yes, s no; collection (p, q, r)
(p, s): q no, r no; no collection
(q, p): r yes, s no; collection (p, q, r)
(q, r): p yes, s no; collection (p, q, r)
(q, s): p no, r no; no collection
(r, p): q yes, s no; collection (p, q, r)
(r, q): p yes, s no; collection (p, q, r)
(r, s): p no, q no; no collection
(s, p): q no, r no; no collection
(s, q): p no, r no; no collection
(s, r): p no, q no; no collection
Try candidate (p, q, r, s): intersection with (p, q, r) has size > 1, reject
Try candidate (p, q, r): intersection with (p, q, r) has size > 1, reject
Try candidate (p, q, s): intersection with (p, q, r) has size > 1, reject
…
Try candidate (p, s): intersection with (p, q, r) has size = 1, accept
Это явно экспоненциальный во времени и пространстве, но это решит проблему.