На плоскости расположено 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:=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
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; 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
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
Не, не намекаю
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.