Задача о красных и синих точках

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования.

«Санкт-Петербургский государственный политехнический университет».

Институт менеджмента и информационных технологий Санкт-Петербургского государственного политехнического университета в г. Череповце.

КУРСОВОЙ ПРОЕКТ.

Дисциплина: Высокоуровневые методы информатики и программирования.

Тема: Задача о красных и синих точках.

Специальность: 80 801 Прикладная информатика (в экономике) Выполнил студент гр. О.581 Марунова Ю. Д.,.

Никитин А.Ю.

2009 год.

• 1.Введение
• 2. Теоретическая часть
• 2.1 Техническое задание
• 2.2 Характеристика программы
• 3. Практическая часть
• 3.1 Структура программы
• 3.2 Описание используемых типов данных
• 3.3 Описание основных алгоритмов
• 4.Резюме
• 4.1 Выводы
• 4.2 Возможные модернизации
• 5. Литература
• 6. Приложение
• 6.1 Текст программы

1. Введение.

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

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

2. Теоретическая часть.

2.1 Техническое задание.

1.

Введение

.

Программа предназначена для определения возможности построения n отрезков с разноцветными концами, суммарная длина которых будет минимальна (из точки может выходить только один отрезок).

2. Основание для разработки.

Выполнение курсовой работы по дисциплине «Высокоуровневые методы информатики и программирования «.

3. Назначение разработки.

Данная программа создана в опытных целях для проверки возможности оптимального варианта построения отрезков.

4. Требования к программе.

4.1. Требования к функциональным характеристикам.

В состав программы входят функции.

— построить n отрезков.

Входные данные — указание размеров a и n.

Выходные данные — графическая информация, выводимая на экран.

4.2. Требования к надежности.

Надежное функционирование программы обеспечивается за счёт ограниченного множества функций программы.

4.3. Требования к составу и параметрам технических средств ЭВМ, внешние устройства, их характеристики.

Для функционирования программы требуется компьютер со следующими минимальными требованиями:

CPU -8086.

RAM-640 KB.

VGAмонитор Прочие внешние устройства для работы программы не требуются.

4.4. Требования к информационной и программной совместимости ОС, система программирования, используемые программные средства, методы решения, информационные структуры и т. п.

Для функционирования программы требуется ОС MS-DOS версии 3.30 или выше, от 64 килобайт свободной оперативной памяти. Программа разработана в интегрированной среде Borland Delphi версии 7.0.

5. Требования к программной документации.

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

6. Технико-экономические показатели. Ориентировочная экономическая эффективность, преимущества по сравнению с аналогами.

7. Стадии и этапы работ (примерный план).

2.2 Характеристика программы

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

2.3 Общий вид программы

Программа, рассчитывающая минимальную суммарную длину отрезков с концами разного цвета, выглядит следующим образом:

· Большое поле (В нем пользователь определяет местоположение точек. После введения равного количества точек 2 цветов здесь эти точки соединяются таким образом, что отрезок получается с концами разных цветов. А сумма этих отрезков минимальна).

· Определение количества точек, введенных пользователем с описанием их цвета.

· 3 режима, выбираемых пользователем:

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

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

3. Ручной режим. Данный режим позволяет пользователю самому как ввести точки так и провести между ними отрезок с разными концами соответственно.

· Кнопка «Очистить» (Полностью очищает оба поля от точек и их координат, а так же сбрасывает счетчики количества точек.).

· Кнопка «Рассчитать» (Даная кнопка действует только после ввода равного количества точек 2 цветов. После ее нажатия программа «расчерчивает» такие отрезки с концами разных цветов, сумма которых минимальна. Ниже Малого поля компьютер показывает размер этой суммы.).

· Кнопка «Шаг». При каждом ее нажатии программа показывает и рассчитывает разные варианты соединения точек.

2.4 Алгоритм работы с программой

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

1. Выбираем один из режимов ввода точек: Режим ввода красных

точек / Режим ввода синих точек.

2. Расставляем в произвольном порядке на Большом поле точки

определенного цвета.

3. Меняем режим на ввод точек следующего цвета и так же расставляем

их на поле в совершенно произвольном порядке.

4. Выбираем ручной или автоматический режим работы.

5. Количество точек разных цветов должно быть одинаковым. В ином случае кнопка «Рассчитать» не активируется.

6. При выполнении условия из пункта № 5, активируется кнопка «Рассчитать». Теперь, при ее нажатии, на Большом поле появляются вышеописанные отрезки, а ниже высвечивается их min сумма.

7. Теперь, после получения окончательного результата, пользователь может очистить Большое и Малое поля с помощью кнопки «Очистить».

8. После того, как пользователь расставил все точки, при каждом нажатии кнопки «Шаг» программа показывает и рассчитывает новые варианты соединения точек.

9. Еще один, ручной режим, пользователь реализует соответственно сам. То есть, после того, как пользователь расставил все точки, при нажатии кнопки «Курсор» он может сам соединять точки в том порядке, в котором захочет, при этом в Малом поле автоматически отображается сумма получившихся отрезков. После «отжатия» этой же кнопки нужно нажать кнопку «Шаг» и тогда программа покажет правильный вариант, т. е. вариант с минимальной суммой отрезков.

2.5 Некоторые особенности данной программы

a. Кнопка «Расчитать» загорается только при равном количестве точек обоих цветов. Это объясняется математически.

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

b. Кнопкой «Очистить» можно воспользоваться в любой момент процесса выполнения алгоритма, что наиболее удобно для пользователя в случае какой-либо ошибки. Но очищается полностью все поле в любом из режимов.

2.6 Математическое обоснование

Для математического обоснования данной задачи мне потребуется изучение темы «Вектора» и соответственно основные формулы: «Длина вектора» или «Расстояние между 2 точками».

Задача (условно): Дано N точек синего цвета и N точек красного цвета, координаты их известны. Нужно соединить их так, чтобы расстояние от точки одного цвета до точки другого цвета было минимальным из возможных вариантов. Далее рассчитать сумму их длин.

Примечание: Если мы соединим точки вышеописанным образом, то при сложении длин получившихся отрезков у нас уже получается минимальная сумма длин этих отрезков.

Решение:

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

Для расчета длины используем формулу длины вектора:

AЇB = v (x2 — x1)2 + (y2 — y1)2 (1).

II. После того, как выбраны нужные (минимальные) варианты длин отрезков, нужно просто суммировать эти длины, в результате, задача решена, получен нужный ответ.

3. Практическая часть.

3.1 Структура программы.

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

Рассмотрим некоторые блоки, встречающиеся в программе.

Интерфейс — этот блок осуществляет взаимодействие пользователя и программы. Взаимодействие осуществляется с помощью монитора, клавиатуры и мыши.

Ввод синих и красных точекв этом блоке запоминаются данные о синих и красных точек и размещаются на поле пользователем.

Построение отрезков — блок, который производит построение отрезков из красных и синих точек.

Отображение хода работы алгоритма — в таблице отражаются отрезки и их суммарная длина.

Визуализация результатов — отображение изменений происходящих в программе.

Справка — производная интерфейса, служит для получения сведений по эксплуатации программы.

3.2 Описание используемых типов данных.

В ходе реализации программы использовались как стандартные структуры данных, так и собственные, созданные непосредственно при проектировании алгоритма.

Для хранения данных о красных и синих точках используется спиcок pList типа TList. Число точек хранится в переменной tCount, число красных точек — в redCount, число синих точек — в blueCount.

Также был создан тип данных TPnt для хранения структуры данных о точке имеющий следующий вид:

PPnt = ^TPnt;

TPnt = record.

X, Y: integer;

rColor: byte;

num: integer;

Linked: boolean;

end;

Как видно он основан на указателях (PPnt ссылается на адресное пространство типа TPnt), и использование этого типа подразумевает хранение следующей информации о точке:

· Координаты X и Y.

· Цвет точки (1 — красный, 2 — синий).

· Связана ли точка (Linked = true/false).

· Номер точки, с которой связана данная точка, если она связана (num).

3.3 Описание основных алгоритмов.

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

Подробное описание автоматического и ручного алгоритмов было приведено ранее, в пункте 2.4.

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

Изобразим работу алгоритма графически:

Рис. 1.

Код процедуры, реализующей данный алгоритм:

procedure FindLines;

Var.

i, j, start: integer;

P, P2, PMin, Pz: PPnt;

Min, Sum: double;

begin.

for start:= 0 to pList. Count-1 do.

begin.

Sum:=0;

tmpList.Clear;

for i:= 0 to pList. Count-1 do.

begin.

Pz := pList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

tmpList.Add (P);

end;

for i:= start to tmpList. Count-2 do.

begin.

P := tmpList. Items[i];

if not P^.Linked then.

begin.

Min := MaxInt;

for j := 0 to tmpList. Count — 1 do.

if i<>j then.

begin.

P2 := tmpList. Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then.

begin.

if sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y)) < Min then.

begin.

Min := sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

for i := 0 to start-1 do.

begin.

P := tmpList. Items[i];

if not P^.Linked then.

begin.

Min := MaxInt;

for j := 0 to tmpList. Count — 1 do.

if i<>j then.

begin.

P2 := tmpList. Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then.

begin.

if sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y)) < Min then.

begin.

Min := sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

if start=0 then.

begin.

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList. Count-1 do.

begin.

Pz := tmpList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

oList.Add (P);

end;

end.

else if sum<minsum then.

begin.

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList. Count-1 do.

begin.

Pz := tmpList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

oList.Add (P);

end;

end;

end;

pList.Clear;

for i:= 0 to oList. Count-1 do.

begin.

Pz := oList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

pList.Add (P);

end;

Form1.Label3.Caption := 'Минимальная сумма отрезков: ' + FloatToStr (minSum);

end;

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

Ниже приведена общая блок-схема алгоритма:

4. Резюме.

4.1 Выводы.

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

К достоинствам программы можно отнести:

— простой интерфейс без излишних сложностей;

— процесс работы программы визуализируется;

К недостаткам можно отнести следующее:

— невозможность более детального анализа алгоритма;

4.2 Возможные модернизации.

программа задача алгоритм.

1. Доработать программу и дать возможность пользователю более детального анализа алгоритма.

5.

Литература

.

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест «Алгоритмы: построение и анализ».

2. В. В. Фаронов «Delphi — программирование на языке высокого уровня».

3. Ю. С. Избачков, В. Н. Петров «Информационные системы», второе издание.

6. Приложение.

6.1 Текст программы.

unit Unit1;

interface.

uses.

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,.

Dialogs, ComCtrls, Menus, ToolWin, ExtCtrls, StdCtrls, ImgList, Grids,.

ValEdit, ShellAPI;

type.

TForm1 = class (TForm).

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

Panel1: TPanel;

ToolBar1: TToolBar;

ToolButton1: TToolButton;

ToolButton2: TToolButton;

Image1: TImage;

Button1: TButton;

Button2: TButton;

ImageList1: TImageList;

ToolButton3: TToolButton;

N3: TMenuItem;

N4: TMenuItem;

ScrollBox1: TScrollBox;

Image2: TImage;

GroupBox1: TGroupBox;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Button3: TButton;

StringGrid1: TStringGrid;

Panel2: TPanel;

procedure ToolButton1Click (Sender: TObject);

procedure ToolButton3Click (Sender: TObject);

procedure FormCreate (Sender: TObject);

procedure Image1MouseUp (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure ToolButton2Click (Sender: TObject);

procedure Button1Click (Sender: TObject);

procedure Button2Click (Sender: TObject);

procedure Button3Click (Sender: TObject);

procedure N4Click (Sender: TObject);

procedure N3Click (Sender: TObject);

private.

{ Private declarations }.

public.

{ Public declarations }.

end;

PPnt = ^TPnt;

TPnt = record.

X, Y: integer;

rColor: byte;

num: integer;

Linked: boolean;

end;

var.

Form1: TForm1;

rColor: byte;

pList, tmpList, oList, rList: TList;

tCount, redCount, blueCount: integer;

cWidth, cHeight: integer;

minSum: double;

start_sh: integer;

i₁, j₁, i₂, j₂: integer;

i, j, start: integer;

P, P2, PMin, Pz: PPnt;

Min, Sum: double;

x, y: integer;

fl:Boolean;

i_col, ip1, ip2:integer;

implementation.

{$R *.dfm}.

procedure ClearGrid;

Var rRect: TRect;

begin.

rRect.Left := cWidth + 1;

rRect.Right := Form1. Image2.Width;

rRect.Top := 0;

rRect.Bottom := Form1. Image2.Height;

Form1.Image2.Canvas.Brush.Color := clWhite;

Form1.Image2.Canvas.FillRect (rREct);

end;

procedure FindLines;

Var.

i, j, start: integer;

P, P2, PMin, Pz: PPnt;

Min, Sum: double;

begin.

for start:= 0 to pList. Count-1 do.

begin.

Sum:=0;

tmpList.Clear;

for i:= 0 to pList. Count-1 do.

begin.

Pz := pList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

tmpList.Add (P);

end;

for i:= start to tmpList. Count-2 do.

begin.

P := tmpList. Items[i];

if not P^.Linked then.

begin.

Min := MaxInt;

for j := 0 to tmpList. Count — 1 do.

if i<>j then.

begin.

P2 := tmpList. Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then.

begin.

if sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y)) < Min then.

begin.

Min := sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

for i := 0 to start-1 do.

begin.

P := tmpList. Items[i];

if not P^.Linked then.

begin.

Min := MaxInt;

for j := 0 to tmpList. Count — 1 do.

if i<>j then.

begin.

P2 := tmpList. Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then.

begin.

if sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y)) < Min then.

begin.

Min := sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

if start=0 then.

begin.

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList. Count-1 do.

begin.

Pz := tmpList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

oList.Add (P);

end;

end.

else if sum<minsum then.

begin.

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList. Count-1 do.

begin.

Pz := tmpList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

oList.Add (P);

end;

end;

end;

pList.Clear;

for i:= 0 to oList. Count-1 do.

begin.

Pz := oList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

pList.Add (P);

end;

Form1.Label3.Caption := 'Минимальная сумма отрезков: ' + FloatToStr (minSum);

end;

procedure DrawGrid (vList: TList);

Var i, j: integer;

rREct: TRect;

p: PPnt;

begin.

for j:=1 to vList. Count do.

begin.

Form1.Image2.Canvas.Pen.Color := clBlack;

rRect.Left := cWidth * j;

rRect.Top := 0;

rRect.Right := cWidth * (j+1);

rRect.Bottom := cHeight;

Form1.Image2.Canvas.FillRect (rRect);

Form1.Image2.Canvas.Brush.Color := clInactiveCaption;

Form1.Image2.Canvas.FillRect (rRect);

Form1.Image2.Canvas.Font.Style := [fsBold];

Form1.Image2.Canvas.TextOut (j * cWidth + round (cWidth/2)-3, 1, IntToStr (j));

for i:=0 to 5 do.

begin.

Form1.Image2.Canvas.MoveTo (cWidth*j, i*cHeight);

Form1.Image2.Canvas.LineTo (cWidth*(j + 1), i*cHeight);

end;

for i:= j to j + 1 do.

begin.

Form1.Image2.Canvas.MoveTo (i*cWidth, 0);

Form1.Image2.Canvas.LineTo (i*cWidth, cHeight*5 + 1);

end;

Form1.Image2.Canvas.Font.Style := [];

Form1.Image2.Canvas.Brush.Color := clWhite;

p := vList. Items[j-1];

Form1.Image2.Canvas.TextOut ((j+1)*cWidth — round (cWidth/2) — 8, cHeight + 1, IntToStr (p^.X));

Form1.Image2.Canvas.TextOut ((j+1)*cWidth — round (cWidth/2) — 8, 2*cHeight + 1, IntToStr (p^.Y));

Form1.Image2.Canvas.TextOut ((j+1)*cWidth — round (cWidth/2) — 2, 3*cHeight + 1, IntToStr (p^.num));

if p^.rColor = 1 then.

begin.

rRect.Left := cWidth * j + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (j+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clRed;

Form1.Image2.Canvas.FillRect (rRect);

end;

if p^.rColor = 2 then.

begin.

rRect.Left := cWidth * j + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (j+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clBlue;

Form1.Image2.Canvas.FillRect (rRect);

end;

end;

end;

procedure DeletePoints (vList: TList);

Var p: PPnt;

begin.

while vList. Count > 0 do.

begin.

P := vList. Items[0];

Dispose (P);

vList.Delete (0);

end;

tCount := 0;

RedCount := 0;

BlueCount := 0;

end;

procedure DrawPoints (vList: TList);

Var i, j: integer;

p, p2: PPnt;

begin.

for i := 0 to vList. Count-1 do.

begin.

p:= vList. Items[i];

if p^.rColor = 1 then.

Form1.Image1.Canvas.Brush.Color := clRed;

if p^.rColor = 2 then.

Form1.Image1.Canvas.Brush.Color := clBlue;

Form1.Image1.Canvas.Pen.Color := clBlack;

Form1.Image1.Canvas.Ellipse (p^.X-4,p^.Y-4,p^.X+4,p^.Y+4);

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.TextOut (p^.X-20, p^.Y-5, IntToStr (i+1));

for j:=i+1 to vList. Count — 1 do.

begin.

p2 := vList. Items[j];

if p^.num = p2^.num then.

begin.

Form1.Image1.Canvas.MoveTo (p^.X, p^.Y);

if p^.rColor = 1 then Form1. Image1.Canvas.Pen.Color := clRed;

if p^.rColor = 2 then Form1. Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo (round ((P^.X+P2^.X)/2), round ((P^.Y+P2^.Y)/2));

if p2^.rColor = 1 then Form1. Image1.Canvas.Pen.Color := clRed;

if p2^.rColor = 2 then Form1. Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo (P2^.X, P2^.Y);

end;

end;

end;

end;

procedure AddDrawPoint (vList: TList; X, Y: integer);

Var p: PPnt;

begin.

Inc (tCount);

Form1.Image1.Canvas.Pen.Color := clBlack;

if rColor = 1 then.

begin.

Inc (RedCount);

Form1.Image1.Canvas.Brush.Color := clRed;

Form1.Image1.Canvas.Ellipse (X-4,Y-4,X+4,Y+4);

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.TextOut (X-20, Y-5, IntToStr (tCount));

New (p);

p^.X := X;

p^.Y := Y;

p^.rColor := 1;

p^.Linked := false;

p^.num := tCount;

pList.Add (p);

end;

if rColor = 2 then.

begin.

Inc (BlueCount);

Form1.Image1.Canvas.Brush.Color := clBlue;

Form1.Image1.Canvas.Ellipse (X-4,Y-4,X+4,Y+4);

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.TextOut (X-20, Y-5, IntToStr (tCount));

New (p);

p^.X := X;

p^.Y := Y;

p^.rColor := 2;

p^.Linked := false;

p^.num := tCount;

pList.Add (p);

end;

end;

procedure AddGridPoint (vList: TList);

Var rRect: TRect;

i: integer;

p: PPnt;

begin.

if rColor = 0 then exit;

cWidth := 50;

cHeight := 15;

rRect.Left := cWidth * vList. Count;

rRect.Top := 0;

rRect.Right := cWidth * (vList.Count+1);

rRect.Bottom := cHeight;

Form1.Image2.Canvas.FillRect (rRect);

Form1.Image2.Canvas.Brush.Color := clInactiveCaption;

Form1.Image2.Canvas.FillRect (rRect);

Form1.Image2.Canvas.Font.Style := [fsBold];

Form1.Image2.Canvas.TextOut (vList.Count * cWidth + round (cWidth/2)-3, 1, IntToStr (vList.Count));

for i:=0 to 5 do.

begin.

Form1.Image2.Canvas.MoveTo (cWidth*vList.Count, i*cHeight);

Form1.Image2.Canvas.LineTo (cWidth*(vList.Count + 1), i*cHeight);

end;

for i:= pList. Count to pList. Count + 1 do.

begin.

Form1.Image2.Canvas.MoveTo (i*cWidth, 0);

Form1.Image2.Canvas.LineTo (i*cWidth, cHeight*5 + 1);

end;

Form1.Image2.Canvas.Font.Style := [];

Form1.Image2.Canvas.Brush.Color := clWhite;

p := vList. Items[vList.Count-1];

Form1.Image2.Canvas.TextOut ((vList.Count+1)*cWidth — round (cWidth/2) — 8, cHeight + 1, IntToStr (p^.X));

Form1.Image2.Canvas.TextOut ((vList.Count+1)*cWidth — round (cWidth/2) — 8, 2*cHeight + 1, IntToStr (p^.Y));

//if p^.Linked.

//then.

Form1.Image2.Canvas.TextOut ((vList.Count+1)*cWidth — round (cWidth/2) — 2, 3*cHeight + 1, IntToStr (p^.num));

//else.

//Form1.Image2.Canvas.TextOut ((vList.Count+1)*cWidth — round (cWidth/2) — 2, 3*cHeight + 1, '-');

if p^.rColor = 1 then.

begin.

rRect.Left := cWidth * vList. Count + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (vList.Count+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clRed;

Form1.Image2.Canvas.FillRect (rRect);

end;

if p^.rColor = 2 then.

begin.

rRect.Left := cWidth * vList. Count + 1;

rRect.Top := cHeight * 4 + 1;

rRect.Right := cWidth * (vList.Count+1);

rRect.Bottom := cHeight*5;

Form1.Image2.Canvas.Brush.Color := clBlue;

Form1.Image2.Canvas.FillRect (rRect);

end;

end;

procedure pointsDraw;

Var i: integer;

p: PPnt;

begin.

Form1.Image1.Canvas.Brush.Color := clWhite;

Form1.Image1.Canvas.FillRect (Form1.Image1.Canvas.ClipRect);

Form1.Image1.Canvas.Rectangle (Form1.Image1.Canvas.ClipRect);

for i:=0 to pList. Count — 1 do.

begin.

p := pList. Items[i];

if p^.rColor = 1 then.

begin.

Form1.Image1.Canvas.Brush.Color := clRed;

Form1.Image1.Canvas.Ellipse (p^.X-4,p^.Y-4,p^.X+4,p^.Y+4);

end;

if p^.rColor = 2 then.

begin.

Form1.Image1.Canvas.Brush.Color := clBlue;

Form1.Image1.Canvas.Ellipse (p^.X-4,p^.Y-4,p^.X+4,p^.Y+4);

end;

end;

end;

procedure TForm1. ToolButton1Click (Sender: TObject);

begin.

Screen.Cursor := crCross;

rColor := 1;

end;

procedure TForm1. ToolButton3Click (Sender: TObject);

var i: Integer;

begin.

if (fl=false) then //кнопка нажата первый раз. включено ручное черчение.

begin.

sum:=0;

i_col:=0;

fl:=true;

Screen.Cursor := crCross;

rColor := 0;

Button2.Enabled:=false;

Button3.Enabled:=false;

start:=1;

StringGrid1.RowCount := 2; //отрисовка таблицы вывода результата.

StringGrid1.ColCount := round (pList.Count/2)+2;

StringGrid1.Cells[StringGrid1.ColCount-1,0] := 'Сумма';

end.

else //выход из режима черчения.

begin //возврат связей в исходное состояние.

for i:= 0 to pList. Count-1 do.

PPnt (pList.Items[i])^.Linked:=false;

start := 0;

Screen.Cursor := crDefault;

fl:=false;

Button2.Enabled:=true;

Button3.Enabled:=true;

end;

end;

procedure TForm1. FormCreate (Sender: TObject);

Var.

rRect: TRect;

i: integer;

begin //пераоночальное присваивание переменных.

fl:=false;

start := 0;

i₁ := start_sh;

j₁ := 0;

i₂ := 0;

j₂ := 0;

tCount := 0;

redCount := 0;

blueCount := 0;

cWidth := 50;

cHeight := 15;

rRect.Left := 0;

rRect.Top := 0;

rRect.Right := Image1. Width;

rRect.Bottom := Image1. Height;

Image1.Canvas.FillRect (rRect);

Image1.Canvas.Rectangle (rREct);

rRect.Left := 0;

rRect.Top := 0;

rRect.Right := Image2. Width;

rRect.Bottom := Image2. Height;

Image2.Canvas.FillRect (rRect);

rRect.Right := cWidth;

rRect.Bottom := cHeight*5;

Image2.Canvas.Brush.Color := clInactiveCaption;

Image2.Canvas.FillRect (rRect);

Image2.Canvas.Font.Style := [fsBold];

for i:=0 to 5 do.

begin.

Image2.Canvas.MoveTo (0, i*cHeight);

Image2.Canvas.LineTo (cWidth, i*cHeight);

end;

for i:= 0 to 1 do.

begin.

Image2.Canvas.MoveTo (i*cWidth, 0);

Image2.Canvas.LineTo (i*cWidth, cHeight*5 + 1);

end;

Image2.Canvas.TextOut (round (cWidth/2)-2, cHeight + 1, 'X');

Image2.Canvas.TextOut (round (cWidth/2)-2, 2*cHeight + 1, 'Y');

Image2.Canvas.TextOut (round (cWidth/2)-14, 3*cHeight + 1, 'Связь');

Image2.Canvas.TextOut (round (cWidth/2)-14, 4*cHeight + 1, 'Цвет');

rColor := 0;

pList := TList. Create;

tmpList := TList. Create;

oList := TList. Create;

rList := TList. Create;

end;

procedure TForm1. Image1MouseUp (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

Var p: PPnt;

p1, p2: PPnt;

i:Integer;

minn, mint: Real;

begin.

if fl then.

begin.

minn:=-1; //переменная расстояния между точками. -1 означает что еще не вычислялась.

if (i_col=1)then //поиск второй точки, максимально близкой к месту нажатия.

begin.

for i:= 0 to pList. Count-1 do //перебор всех точек.

begin.

p:= pList. Items[i]; //данные i-й точки.

if (p^.Linked=false)and (p^.rColor<>PPnt (pList.Items[ip1])^.rColor) //если точка не связана и противоположного цвета тогда.

then.

begin.

mint:=sqrt (sqr (P^.X — X) + sqr (P^.Y — Y)); //вычисление расстояния.

if (minn<0)then //первоночальное присваивание.

begin.

ip2:=i; //запомнить позиции точки из списка.

minn:=mint.

end;

if (mint<minn)then //поиск очередного минимума.

begin.

ip2:=i;

minn:=mint.

end;

end;

end;

inc (i_col); //переход к друнгомк режиму обработки.

PPnt (pList.Items[ip2])^.Linked:=true;

end;

if (i_col=0)then //поиск первой точки, максимально близкой к месту нажатия.

begin.

for i:= 0 to pList. Count-1 do //поиск первой точки.

begin.

p:= pList. Items[i];

if (p^.Linked=false).

then.

begin.

mint:=sqrt (sqr (P^.X — X) + sqr (P^.Y — Y));

if (minn<0)then //первоночальное присваивание.

begin.

ip1:=i;

minn:=mint.

end;

if (mint<minn)then.

begin.

ip1:=i;

minn:=mint.

end;

end;

end;

inc (i_col);

PPnt (pList.Items[ip1])^.Linked:=true;

end;

if (i_col=2) then //2 точки отобраны?

begin //отрисовка линии.

p1 := pList. Items[ip1];

p2 := pList. Items[ip2];

sum:=sum+sqrt (sqr (P1^.X — P2^.X) + sqr (P1^.YP2^.Y));

Form1.Image1.Canvas.MoveTo (p1^.X, p1^.Y);

if p1^.rColor = 1 then Form1. Image1.Canvas.Pen.Color := clRed;

if p1^.rColor = 2 then Form1. Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo (round ((P1^.X+P2^.X)/2), round ((P1^.Y+P2^.Y)/2));

if p2^.rColor = 1 then Form1. Image1.Canvas.Pen.Color := clRed;

if p2^.rColor = 2 then Form1. Image1.Canvas.Pen.Color := clBlue;

Form1.Image1.Canvas.LineTo (P2^.X, P2^.Y);

//отображение цифр в таблице.

StringGrid1.Cells[start, 1] := IntToStr (P1^.num)+'-'+IntToStr (P2^.num);

StringGrid1.Cells[StringGrid1.ColCount-1,1] := IntToStr (round (Sum));

inc (start);

i_col:=0;

end;

end.

else.

begin.

AddDrawPoint (pList, X, Y);

AddGridPoint (pList);

Label1.Caption := 'Красные точки: ' + IntToStr (redCount);

Label2.Caption := 'Синие точки: ' + ' ' + IntToStr (blueCount);

if redCount = blueCount then Button2. Enabled := true else Button2. Enabled := false;

end;

end;

procedure TForm1. ToolButton2Click (Sender: TObject);

begin.

rColor := 2;

Screen.Cursor := crCross;

end;

procedure TForm1. Button1Click (Sender: TObject);

Var i: integer;

p: PPnt;

begin.

Start := 0;

start_sh := 0;

i₁ := Start_sh;

i₂ := 0;

j₁ := 0;

j₂ := 0;

DeletePoints (pList);

Image1.Canvas.Pen.Color := clBlack;

Image1.Canvas.Brush.Color := clWhite;

Image1.Canvas.Rectangle (Image1.Canvas.ClipRect);

ClearGrid;

end;

procedure TForm1. Button2Click (Sender: TObject);

Var rRect: TRect;

i: integer;

begin.

FindLines;

DrawPoints (pList);

ClearGrid;

DrawGrid (pList);

end;

procedure TForm1. Button3Click (Sender: TObject);

Var rRect: TRect;

begin.

if Start = pList. Count then //перебор точек по нажатию кнопки «Шаг» завершено.

begin.

Label3.Caption := 'Минимальная сумма отрезков: ' + FloatToStr (minSum);

exit;

end;

Sum:=0;

tmpList.Clear;

for i:= 0 to pList. Count-1 do //передача всех точек во временный список.

begin.

Pz := pList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

tmpList.Add (P);

end;

for i:= start to tmpList. Count-2 do //.

begin.

P := tmpList. Items[i];

if not P^.Linked then.

begin.

Min := MaxInt;

for j := 0 to tmpList. Count — 1 do.

if i<>j then.

begin.

P2 := tmpList. Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then.

begin.

if sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y)) < Min then.

begin.

Min := sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

for i := 0 to start-1 do.

begin.

P := tmpList. Items[i];

if not P^.Linked then.

begin.

Min := MaxInt;

for j := 0 to tmpList. Count — 1 do.

if i<>j then.

begin.

P2 := tmpList. Items[j];

if (not P2^.Linked) and (P2^.rColor <> P^.rColor) then.

begin.

if sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y)) < Min then.

begin.

Min := sqrt (sqr (P^.X — P2^.X) + sqr (P^.Y — P2^.Y));

PMin := P2;

end;

end;

end;

Sum:=Sum+Min;

P^.Linked := True;

PMin^.Linked := True;

PMin^.Num := P^.Num;

end;

end;

if start=0 then.

begin.

minsum:=sum;

oList.Clear;

i₁ := 0;

for i:= 0 to tmpList. Count-1 do.

begin.

Pz := tmpList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

oList.Add (P);

end;

end.

else if sum<minsum then.

begin.

minsum:=sum;

oList.Clear;

for i:= 0 to tmpList. Count-1 do.

begin.

Pz := tmpList. Items[i];

New (P);

P^.X :=Pz.X ;

P^.Y :=Pz.Y;

P^.rColor :=Pz.rColor;

P^.Linked := Pz. Linked;

P^.Num := Pz. Num;

oList.Add (P);

end;

end;

i₁ := 0;

StringGrid1.RowCount := start+2;

StringGrid1.ColCount := REdCount+2;

for i:= 0 to oList. Count-1 do.

begin.

p := oList. Items[i];

if P^.num <> i+1 then.

begin.

Inc (i₁);

StringGrid1.Cells[i₁, start+1]: = IntToStr (i+1) + '-' + IntToStr (p^.num);

StringGrid1.Cells[StringGrid1.ColCount-1,start+1] := FloatToStr (round (minSum));

StringGrid1.Cells[i₁, 0]: = IntToStr (i₁);

StringGrid1.Cells[StringGrid1.ColCount-1,0] := 'Сумма';

end;

end;

StringGrid1.Cells[0,start+1]: = IntToStr (start+1);

DrawGrid (oList);

Image1.Canvas.FillRect (Image1.Canvas.ClipRect);

DrawPoints (oList);

inc (start);

end;

procedure TForm1. N4Click (Sender: TObject);

begin.

ShellExecute (Handle, 'open','index.chm', nil, Nil, SW_ShowNormal);

end;

procedure TForm1. N3Click (Sender: TObject);

begin.

Form1.Close;

end;

end.