На плоскости расположено 2N точек, N порядка 10^5. Никакие две точки не совпадают. Три и больше точек *могут* лежать на одной прямой.
Нужно выбрать такое "паросочетание" точек (т.е. соединить каждую точку с какой-то одной другой), чтобы отрезки не пересекались.
Как это сделать проще всего?
Malice
30.12.2006 15:30
Цитата(Michael_Rybak @ 29.12.2006 16:41)
Как это сделать проще всего?
Спойлер(Показать/Скрыть)
Проще всего соединить из змейкой, т.е. идешь сверху вниз и слева направо и соединяешь то, что попадается ( через раз, конечно). Вот небольшая иллюстрация такого способа:
uses crt,graph;
const n=100;
var i,j,k,x,y:integer;
b:boolean;
begin
i:=0; initgraph (i,i,''); randomize;
for i:=1to n dobeginrepeat
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:=1to640dofor k:=1to480dobeginif odd(i) then j:=k else j:=481-k;
if (getpixel(i,j)=15) and b thenbegin x:=i; y:=j; b:=false; endelseif (getpixel(i,j)=15) andnot(b) thenbegin line(x,y,i,j); b:=true; end;
end;
readkey;
closegraph;
end.
Конечно, правильней делать не так, но для примера работы пойдет
Michael_Rybak
30.12.2006 18:13
Угу, я тоже так думаю
Lapp
30.12.2006 19:12
Спойлер(Показать/Скрыть)
Идти слева направо по х, если на одном х несколько точек - соединять их снизу вверх.
Michael_Rybak
30.12.2006 19:27
Краткость - сестра Lapp'a.
Lapp
30.12.2006 20:32
Цитата(Michael_Rybak @ 30.12.2006 16:27)
Краткость - сестра 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;
beginfor i:=k to l dofor j:=l-1downto i doif x[j]>x[j+1] thenbegin
b:=x[j];
x[j]:=x[j+1];
x[j+1]:=b;
b:=y[j];
y[j]:=y[j+1];
y[j+1]:=b
endend;
begin
d:=0;
InitGraph(d,m,'');
for i:=1to2*n dobegin
x[i]:=Random(GetMaxX+1);
y[i]:=Random(GetMaxY+1)
end;
Sort(x,1,2*n);
i:=1;
while i<2*n dobegin
j:=i;
while (x[j]=x[j+1])and(i<2*n) do Inc(j);
Sort(y,i,j);
i:=j+1end;
for i:=1to n do Line(x[2*i-1],y[2*i-1],x[2*i],y[2*i]);
ReadLn
end.
Michael_Rybak
30.12.2006 20:38
Уел это как? По-моему, достаточно как раз было первого поста
Lapp
30.12.2006 20:57
Цитата(Michael_Rybak @ 30.12.2006 17:38)
Уел это как? По-моему, достаточно как раз было первого поста
Не совсем достаточно.. Тема-то в Задачах. Если б была в Алгоритмах - тогда да. Я подумал, ты на это намекаешь..
Michael_Rybak
30.12.2006 21:43
Не, не намекаю
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.