множество точек на плоскости

[sergei15]

задано множество точек на плоскости. перечислить все различные максимальные подмножества точек, лежащих на одной прямой, которые содержат более двух точек.

[Serge_Bliznykov]

а что такое "максимальное подмножество" ?!

берете две точки, выводите для них уравнение прямой, проверяете, попадают ли ещё точки на эту прямую. считаете количество попавших точек. если это значение больше максимального значения (в начале присвоить ему ноль) - то обнулить все сохранённые комбинации и запомнить текущую комбинацию точек.
если значение равно максмальному, проверить, была ли такая комбинация ранее, если нет - сохранить эту комбинацию.


А конекретная реализация будет зависеть в первую очередь от числа точек и от того, как они представлены. Как и где накапливать найденные подмножества (если их вообще нужно накапливать - потому как можно первый раз пройтись в цикле, найти максимальное КОЛИЧЕСТВО точек, лежащих на одной прямой,
потом ещё раз в цикле по всем парам точек пройтись - выдавая на экран те подмножества, где количество точек на одной прямой равно максимальному количеству, найденному при первом цикле перебора...

[sergei15]

есть код похожий проги. как переделать под мою? очень надо

uses crt;
function Prin(ax,ay,bx,by,cx,cy:integer):boolean;
begin
if (cx-ax)*(by-ay)-(bx-ax)*(cy-ay)=0{формула определения принадлежат ли три точки одной прямой,
из геометрии}
then Prin:=true else Prin:=false;
end;
 
var a:array[1..100,1..2] of integer;
    n,i,j,k,p:integer;
    max:integer;
begin
clrscr;
randomize;
repeat
write('Kolichestvo tochek mnozestva ot 3 do 100 n=');
readln(n);
until n in [1..100];
writeln('Mnozestvo tochek:');
for i:=1 to n do
for j:=1 to 2 do
a[i,j]:=random(10);
write('X  ');
for i:=1 to n do write(a[i,1]:3);
writeln;
write('Y  ');
for i:=1 to n do write(a[i,2]:3);
writeln;
{поиск прямой с макс. кол. точек}
max:=1;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
 begin
  p:=1;
  for k:=j+1 to n do
  if Prin(a[i,1],a[i,2],a[j,1],a[j,2],a[k,1],a[k,2])then
  p:=p+1;
  if p>max then max:=p;
 end;
writeln('Minimalno mozno ubrat ',n-max,' tochek.');
readln
end.

[TinMan]

Сообщение от sergei15

есть код похожий проги. как переделать под мою? очень надо

мне особенно нравится, когда вместо ответа на вопрос начинают пихать всякие затычки..

Серж, "максимальное", думаю, означает, что если есть 10 точек на одной прямой, то комбинации из 3, 4...8, 9 входящих в этот десяток точек перечислять не надо.

P.S.
Сергей15, не похоже, что "очень надо". Надо было бы - либо сделал бы, либо хоть на вопросы отвечал..

[Serge_Bliznykov]

Сообщение от TinMan

Серж, "максимальное", думаю, означает, что если есть 10 точек на одной прямой, то комбинации из 3, 4...8, 9 входящих в этот десяток точек перечислять не надо.

Ага. согласен. спасибо. теперь более менее понятно.
А "различные максимальные подмножества" — это, вероятно, ВСЕ наборы точек, количеством более трёх, лежащие на одной прямой (т.е. хоть там три точки лежит на прямой, хоть 25 точек (на другой прямой) - все эти наборы должны быть выведены.

самое сложное - это как отсечь те наборы, которые уже были ранее.. интуитивно чувствую, что для этого должно быть какое-то несложное условие проверки... (можно, конечно, банально сохранять пару точек, для который вывод набора уже был ранее, но тогда нужно организовывать динамическую структуру. да и не очень это красиво и эффективно...

Ничего в голову не приходит - как отбрасывать отработанные варианты?

Сообщение от TinMan

не похоже, что "очень надо". Надо было бы - либо сделал бы, либо хоть на вопросы отвечал..

Боюсь, что автор топика вообще не понимает, о чём мы тут говорим... к сожалению...

[s-andriano]

Сообщение от Serge_Bliznykov

самое сложное - это как отсечь те наборы, которые уже были ранее..

Ну да.
Мне кажется, оптимальное решение проблемы состоит в том, чтобы избавиться от этой проблемы в зародыше.
В данном случае - не отсекать дубли, а не допускать их с самого начала.
А для этого нужно на каждом этапе исключать из рассмотрентя точки.
1. Цикл по первой точке отрезка прямой.
2. Вложенный цикл по второй точке на отрезке - ее номер всегда больше, чем у первой (номера меньше первой исключаем).
3. Вложенный цикл по оставшимся точкам - окажутся ли они на прямой, проходящей через первые две точки. Номера всех этих точек больше номера второй (номера меньше второй исключаем).
При таком порядке перебора формируемая последовательность точек всегда оказывается упорядоченной по номерам, т.е. исключает появление "перестановок".
Ну и объем вычислений - по минимуму. Правда, сложность все равно O(n^3).

[TinMan]

Задачка меня зацепила )). Думал над ней несколько часов, благо как раз пришлось несколько длительных поездок на машине - прекрасное время для долбежки по задаче: руки не хватаются за клаву сразу )). Но все же сначала сделал вариант, от которого потом пришел в ужас и стер нафик. Запасайтесь кофе и терпением, господа..
Сначала отвечу на последний пост:

Сообщение от s-andriano

избавиться от этой проблемы в зародыше.
В данном случае - не отсекать дубли, а не допускать их с самого начала.
А для этого нужно на каждом этапе исключать из рассмотрентя точки.
1. Цикл по первой точке отрезка прямой.
2. Вложенный цикл по второй точке на отрезке - ее номер всегда больше, чем у первой (номера меньше первой исключаем).
3. Вложенный цикл по оставшимся точкам - окажутся ли они на прямой, проходящей через первые две точки. Номера всех этих точек больше номера второй (номера меньше второй исключаем).
При таком порядке перебора формируемая последовательность точек всегда оказывается упорядоченной по номерам, т.е. исключает появление "перестановок".
Ну и объем вычислений - по минимуму. Правда, сложность все равно O(n^3).

(болд мой - TinMan) Гм. Насчет объема вычислений, ты, может, и прав, но сам алгоритм, боюсь, не катит. Начать с того, что совершенно не ясно, что ты имеешь в виду под упоминаемым "отрезком прямой" и точкам на нем. Не настала ли пора перечитать условие, Сан-Андриано? )) Если ты имел в виду сначала упорядочить точки (неважно, как, собссно), то хоть бы упомянул это. Впрочем, боюсь, это слабо помогает..

Хотя в принципе я согласен - различные варианты надо пресекать на корню. Вопрос - как?

Сообщение от Serge_Bliznykov

самое сложное - это как отсечь те наборы, которые уже были ранее.. интуитивно чувствую, что для этого должно быть какое-то несложное условие проверки... (можно, конечно, банально сохранять пару точек, для который вывод набора уже был ранее, но тогда нужно организовывать динамическую структуру. да и не очень это красиво и эффективно...

Ничего в голову не приходит - как отбрасывать отработанные варианты?

Серж, я, как уже сказал, согласен, что надо попытаться избежать повторяющихся вариантов с самого начала. Но для этого надо пересмотреть всю логику решения..

Главное, что я вынес из неудачи с решением (примерно) по описаной выше схеме, можно выразить так: не надо определять принадлежность точки к прямой, проходящей через две выбранных. Основные положения решения таковы:

1. Определить понятие ЛИНИИ (прямой). То есть, сделать некую числовую структуру, по которой однозначно рисуется линия.

2. Сделать понятие линии однозначным. То есть, если две линии равны, то структуры, их определяющие, также должны быть равны. Предусмотреть функцию определения равенства линий.

3. Рассчитать матрицу линий.

4. Создать матрицу элементов типа boolean, отмечающую использованность каждого элемента матрицы линий (каждая линия используется только один раз - в отличие от каждой точки, которая может быть использована сколько угодно раз).

5. Во вложенном цикле по элементам матрицы линий накапливать множество номеров точек, относящихся к равным линиям. Если во внешнем цикле получается множество из более, чем двух точек - выводить его на печать. (Тут подразумевается, что всего точек не более 255)

6. Скомпилировать, запустить, отвесить челюсть, почесать репу и балдеть.

(сообщение пришлось разбить на два, посколку я превысил длину 5000 символов, так что код будет приведен в следующем посте)

[TinMan]

(начало см. в предыдущем посте)
А вот и код:

// finding maximal sets of points on the same line
// by TinMan, programmersforum.ru

const
  n= 8;
  e= 1e-5;  // small positive number

type
  tReal= single;
  tPoint= record
    x,y: tReal
  end;
  tLine= record
    r,t: tReal
  end;

function Dist(a,b: tPoint): tReal;
begin
  Dist:= Sqrt(Sqr(a.x-b.x)+Sqr(a.y+b.y))
end;

function NormalLineByPoints(a,b: tPoint): tLine;
const
  c: tPoint= (x:0;y:0);
var
  p,x,y,z: tReal;
  d: tPoint;
begin
  x:= Dist(a,b);
  y:= Dist(b,c);
  z:= Dist(c,a);
  p:= (x+y+z)/2.0;
  with NormalLineByPoints do begin
    r:= Sqrt(p*(p-x)*(p-y)*(p-z))/x*2.0;
    if Abs(b.x-a.x)>Abs(b.y-a.y) then begin
      if b.x<a.x then begin
        d:= a;
        a:= b;
        b:= d
      end;
      t:= ArcTan((b.y-a.y)/(b.x-a.x));
      if t<0 then t:= t+Pi
    end
    else begin
      if b.y<a.y then begin
        d:= a;
        a:= b;
        b:= d
      end;
      t:= Pi/2-ArcTan((b.x-a.x)/(b.y-a.y))
    end
  end
end;

function EqualLines(a,b: tLine): boolean;
begin
  EqualLines:= (Abs(b.r-a.r)<e) and (Abs(b.t-a.t)<e)
end;

var
  p: array[1..n] of tPoint=
    ((x:0;y:0),(x:1;y:0),(x:2;y:0),(x:1;y:1),(x:2;y:2),(x:2;y:4),(x:3;y:2),(x:0;y:9));
  l: array[1..n,1..n] of tLine;
  used: array[1..n,1..n] of boolean;
  i,j,u,v: integer;
  s: set of byte;

begin
  // calculating all the lines
  for i:=1 to n do
    for j:=1 to i-1 do l[i,j]:= NormalLineByPoints(p[i],p[j]);

  // looking for equal lines
  for i:=1 to n do
    for j:=1 to i-1 do
      if not used[i,j] then begin
        s:= [];
        for u:=i to n do
          for v:=1 to u-1 do
            if EqualLines(l[i,j],l[u,v]) then begin
              used[u,v]:= true;
              Include(s,u);
              Include(s,v)
            end;
        if s<>[i]+[j] then begin
          writeln('set:');
          for u:=1 to n do
            if u in s then with p[u] do writeln('#',u,':   x=',x:5:2,'  y=',y:5:2);
          writeln
        end
      end;
  readln
end.

Ну и еще пара замечаний для особо любопытных..

а. Для определения структуры линии я использовал нечто похожее на т.н. нормальное уравнение линии (см. wikipedia.ru). Для вычисления расстояния от точки до линии использовал формулу Герона-Архимеда, наклон прямой через банальный ArcTan.

б. По ходу возник вопрос - а что делать, если точки совпадают? Сначала я хотел это как-то разумно решить (и таки решил, если у каждой точки не более одной копии), но потом подумал, что овчинка не стоит выделки, и бросил на полпути - то есть решил, что в условие следует добавить, что все точки различны. Вариант, корректно (вроде) работающий для указанного выше случая остался (могу привести).

[s-andriano]

Сообщение от TinMan

Начать с того, что совершенно не ясно, что ты имеешь в виду под упоминаемым "отрезком прямой" и точкам на нем. Не настала ли пора перечитать условие, Сан-Андриано? )) Если ты имел в виду сначала упорядочить точки (неважно, как, собссно), то хоть бы упомянул это.

Ну, начнем с того, что задача размещена в разделе Паскаль, а потому подразумевается решение не столько математическое, сколько алгоритмическое.
Т.е. нужен алгоритм, который как-то обрабатывает множество точек. Причем это множество для его алгоритмической обработки уже должно быть упорядоченным (неважно, как, собссно), поэтому такой порядок мы будем считать естественным и не будем его нарушать. Т.к. незачем.
Под отрезком прямой я подразумеваю упорядоченное множество из двух точек, являющееся подмножеством исходного множества точек.
При решении задачи перебираются все возможные отрезки. Для чего используется вложенный цикл, во внешнем - перебор по первой точке, во внутреннем - по второй. При этом номер второй точки в естественном порядка всегда больше номера первой. Так мы будем уверены, что каждый из отрезков рассматривается только один раз.

1. Определить понятие ЛИНИИ (прямой). То есть, сделать некую числовую структуру, по которой однозначно рисуется линия.

Линия на плоскости однозначно определяется двумя коэффициентами.

2. Сделать понятие линии однозначным. То есть, если две линии равны, то структуры, их определяющие, также должны быть равны. Предусмотреть функцию определения равенства линий.

Здесь есть некоторая проблема, связанная с особенностями представления дробных чисел в компьютере. Проблема, конечно, решаемая, но все-таки.

3. Рассчитать матрицу линий.

Что такое матрица линий?
Почему матрица?
Из каких элементов она состоит?
Я так понимаю, раз матрица, количество ее элементов O(n^2)?

4. Создать матрицу элементов типа boolean, отмечающую использованность каждого элемента матрицы линий (каждая линия используется только один раз - в отличие от каждой точки, которая может быть использована сколько угодно раз).

Зачем?

5. Во вложенном цикле по элементам матрицы линий накапливать множество номеров точек, относящихся к равным линиям. Если во внешнем цикле получается множество из более, чем двух точек - выводить его на печать. (Тут подразумевается, что всего точек не более 255)

Вложенный цикл по элементам матрицы - это уже O(n^4). Мне это не нравится. При такой сложности ограничение в 255 точек выглядит вполне разумным. А если все-таки алгоритм O(n^3)?

б. По ходу возник вопрос - а что делать, если точки совпадают? Сначала я хотел это как-то разумно решить (и таки решил, если у каждой точки не более одной копии), но потом подумал, что овчинка не стоит выделки, и бросил на полпути - то есть решил, что в условие следует добавить, что все точки различны. Вариант, корректно (вроде) работающий для указанного выше случая остался (могу привести).

Мне кажется, это ограничение никак не вытекает из условия задачи, а, следовательно, ему противоречит.

Из словесного описания алгоритм не понял. Будет время - посмотрю текст программы.

По поводу точек с повторяющимися координатами:
Мне кажется, тут можно устранить проблему предварительной обработкой массива точек - из него "выбрасываются" дубли, но при этом записывается кратность каждой точки. Сложность O(n*log(n)), пусть даже O(n^2).
Итого, точку можно описать структурой:
- координаты: 2D-вектор,
- номер в исходной последовательности (именно его будем использовать при выводе результата): целое число,
- кратность точки: целое число,
- индекс следующей "выброшенной" точки - для организации списка: целое число.

[s-andriano]

Андрей, похоже, мы несколько по-разному понимаем условие задачи.
ТС пишет:

Сообщение от sergei15

все различные максимальные подмножества точек, лежащих на одной прямой

Дадее пишет Serge_Bliznykov

Сообщение от Serge_Bliznykov

первый раз пройтись в цикле, найти максимальное КОЛИЧЕСТВО точек, лежащих на одной прямой,
потом ещё раз в цикле по всем парам точек пройтись - выдавая на экран те подмножества, где количество точек на одной прямой равно максимальному количеству, найденному при первом цикле перебора...

и ему, вроде, никто не возражает.

Я оформил Ваш код в виде процедуры, для чего, правда, пришлось вынести массивы в глобальные переменные, т.к. иначе у меня стек переполнялся уже при количестве точек 123.
В Вашем же решении выдаются ВСЕ множества точек при количестве последних больше 2, что видно уже при количестве точек равном 9.

Смотрим дальше.
При количестве точек равном 40 Ваш код не находит комбинации по 5 точек, а при 70 - по 6.
Ну а вариант с 256 точками дает восзиожность оценить ресурсоемкость алгоритма по времени и памяти.

uses windows;
const
  n0 = 256;
  e= 1e-5;

type
  tReal= single;
  tPoint= record
    x,y: tReal
  end;
  tLine= record
    r,t: tReal
  end;

function Dist(a,b: tPoint): tReal;
begin
  Dist:= Sqrt(Sqr(a.x-b.x)+Sqr(a.y+b.y))
end;

function NormalLineByPoints(a,b: tPoint): tLine;
const
  c: tPoint= (x:0;y:0);
var
  p,x,y,z: tReal;
  d: tPoint;
begin
  x:= Dist(a,b);
  y:= Dist(b,c);
  z:= Dist(c,a);
  p:= (x+y+z)/2.0;
  with result{NormalLineByPoints} do begin
    r:= Sqrt(p*(p-x)*(p-y)*(p-z))/x*2.0;
    if Abs(b.x-a.x)>Abs(b.y-a.y) then begin
      if b.x<a.x then begin
        d:= a;
        a:= b;
        b:= d
      end;
      t:= ArcTan((b.y-a.y)/(b.x-a.x));
      if t<0 then t:= t+Pi
    end
    else begin
      if b.y<a.y then begin
        d:= a;
        a:= b;
        b:= d
      end;
      t:= Pi/2-ArcTan((b.x-a.x)/(b.y-a.y))
    end
  end
end;

function EqualLines(a,b: tLine): boolean;
begin
  EqualLines:= (Abs(b.r-a.r)<e) and (Abs(b.t-a.t)<e)
end;

procedure GetData(k : longint; var p : array of tPoint);
const MaxP = 256;
const
  pp: array[0..MaxP-1] of tPoint=
    ((x:0;y:0),(x:1;y:0),(x:2;y:0),(x:1;y:1),(x:2;y:2),(x:2;y:4),(x:3;y:2),(x:0;y:9),(x:3;y:3),(x:35;y:10),
     (x:52;y:14),(x:40;y:23),(x:41;y:13),(x:42;y:18),(x:36;y:19),(x:36;y:26),(x:36;y:15),(x:53;y:17),(x:50;y:16),(x:48;y:26),
     (x:49;y:16),(x:38;y:16),(x:44;y:14),(x:51;y:15),(x:44;y:12),(x:52;y:15),(x:50;y:29),(x:44;y:27),(x:51;y:10),(x:37;y:12),
     (x:45;y:10),(x:46;y:10),(x:50;y:23),(x:50;y:24),(x:46;y:14),(x:48;y:21),(x:54;y:22),(x:54;y:14),(x:48;y:15),(x:36;y:25),
     (x:97;y:59),(x:85;y:68),(x:86;y:58),(x:87;y:63),(x:81;y:64),(x:81;y:71),(x:81;y:60),(x:98;y:62),(x:95;y:61),(x:93;y:71),
     (x:94;y:61),(x:83;y:61),(x:89;y:59),(x:96;y:60),(x:89;y:57),(x:97;y:60),(x:95;y:74),(x:89;y:72),(x:96;y:55),(x:82;y:57),
     (x:90;y:55),(x:91;y:55),(x:95;y:68),(x:95;y:69),(x:91;y:59),(x:93;y:66),(x:99;y:67),(x:99;y:59),(x:93;y:60),(x:81;y:70),
     (x:130;y:105),(x:147;y:109),(x:135;y:118),(x:136;y:108),(x:137;y:113),(x:131;y:114),(x:131;y:121),(x:131;y:110),(x:148;y:112),(x:145;y:111),
     (x:143;y:121),(x:144;y:111),(x:133;y:111),(x:139;y:109),(x:146;y:110),(x:139;y:107),(x:147;y:110),(x:145;y:124),(x:139;y:122),(x:146;y:105),
     (x:132;y:107),(x:140;y:105),(x:141;y:105),(x:145;y:118),(x:145;y:119),(x:141;y:109),(x:143;y:116),(x:149;y:117),(x:149;y:109),(x:143;y:110),
     (x:180;y:155),(x:197;y:159),(x:185;y:168),(x:186;y:158),(x:187;y:163),(x:181;y:164),(x:181;y:171),(x:181;y:160),(x:198;y:162),(x:195;y:161),
     (x:193;y:171),(x:194;y:161),(x:183;y:161),(x:189;y:159),(x:196;y:160),(x:189;y:157),(x:197;y:160),(x:195;y:174),(x:189;y:172),(x:196;y:155),
     (x:182;y:157),(x:190;y:155),(x:230;y:205),(x:247;y:209),(x:235;y:218),(x:236;y:208),(x:237;y:213),(x:231;y:214),(x:231;y:221),(x:231;y:210),
     (x:248;y:212),(x:245;y:211),(x:243;y:221),(x:244;y:211),(x:233;y:211),(x:239;y:209),(x:246;y:210),(x:239;y:207),(x:247;y:210),(x:245;y:224),
     (x:239;y:222),(x:246;y:205),(x:232;y:207),(x:240;y:205),(x:241;y:205),(x:245;y:218),(x:245;y:219),(x:241;y:209),(x:243;y:216),(x:249;y:217),
     (x:280;y:255),(x:297;y:259),(x:285;y:268),(x:286;y:258),(x:287;y:263),(x:281;y:264),(x:281;y:271),(x:281;y:260),(x:298;y:262),(x:295;y:261),