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

[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.

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