Попарно соединить точки на плоскости Опции

[Michael_Rybak]

Имо, очень прикольная задачка:

На плоскости расположено 2N точек, N порядка 10^5. Никакие две точки не совпадают. Три и больше точек *могут* лежать на одной прямой.

Нужно выбрать такое "паросочетание" точек (т.е. соединить каждую точку с какой-то одной другой), чтобы отрезки не пересекались.

Как это сделать проще всего?

[Malice]

Как это сделать проще всего?

Спойлер (Показать/Скрыть)

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

uses crt,graph;
const n=100;
var i,j,k,x,y:integer;
b:boolean;
begin
i:=0; initgraph (i,i,''); randomize;
for i:=1 to n do begin
repeat
x:=random (620)+10; y:=random(460)+10;
until getpixel (x,y)=0;
putpixel (x,y,15);
end;
readkey; x:=0; y:=0; b:=true;
for i:=1 to 640 do
 for k:=1 to 480 do begin
if odd(i) then j:=k else j:=481-k;
if (getpixel(i,j)=15) and b then begin x:=i; y:=j; b:=false; end else
if (getpixel(i,j)=15) and not(b) then begin line(x,y,i,j); b:=true; end;
end;
readkey;
closegraph;
end.

Конечно, правильней делать не так, но для примера работы пойдет

[Michael_Rybak]

Угу, я тоже так думаю

[Lapp]

Спойлер (Показать/Скрыть)

Идти слева направо по х, если на одном х несколько точек - соединять их снизу вверх.

[Michael_Rybak]

Краткость - сестра Lapp'a.

[Lapp]

Краткость - сестра Lapp'a.

Уел .
Ладно, получай то, чему приличествует быть в Задачах..

Спойлер (Показать/Скрыть)

uses
  Graph;

const
  n=1000;

type
  arr=array[1..2*n]of integer;

var
  c,d,m,i,j:integer;
  x,y:arr;

procedure Sort(var a:arr; k,l:integer);
var
  b,i,j:integer;
begin
  for i:=k to l do for j:=l-1 downto i do if x[j]>x[j+1] then begin
    b:=x[j];
    x[j]:=x[j+1];
    x[j+1]:=b;
    b:=y[j];
    y[j]:=y[j+1];
    y[j+1]:=b
  end
end;

begin
  d:=0;
  InitGraph(d,m,'');
  for i:=1 to 2*n do begin
    x[i]:=Random(GetMaxX+1);
    y[i]:=Random(GetMaxY+1)
  end;
  Sort(x,1,2*n);
  i:=1;
  while i<2*n do begin
    j:=i;
    while (x[j]=x[j+1])and(i<2*n) do Inc(j);
    Sort(y,i,j);
    i:=j+1
  end;
  for i:=1 to n do Line(x[2*i-1],y[2*i-1],x[2*i],y[2*i]);
  ReadLn
end.

[Michael_Rybak]

Уел это как?
По-моему, достаточно как раз было первого поста

[Lapp]

Уел это как?
По-моему, достаточно как раз было первого поста

Не совсем достаточно.. Тема-то в Задачах. Если б была в Алгоритмах - тогда да.
Я подумал, ты на это намекаешь..

[Michael_Rybak]

Не, не намекаю