Урок #7  «Вычислительная геометрия в программировании»

Глава #1  «Многоточие...»

*проще простого*

Мы снова на олимпиаде и   что мы видим тема одной из задач «Вычислительная геометрия», то есть в задачах чаще всего даются координаты N точек (Х,У) и требуется:

A)  найти максимальную площадь треугольника, составленного из любых трех точек

Б) найти длину максимального или минимального отрезка образованного парой точек

B)  определить лежит ли точка внутри фигуры или нет

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

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

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

Например как описать массив координат N точек?

X,Y:ARRAY[1..100] OF INTEGER;

Заполняют массив чаще всего с помощью циклов. Пример:

READ(N);

FOR I: = l  ТО N DO READ(X[I],Y[I]); - массивы X и Y заполнены из INPUT.TXT, там координаты N

точек в виде таблицы, вначале читают количество точек, потом их координаты.

Например:

INPUT.TXT

3

11

2 О

2 2

Обращаются к элементам массивов парно называя и X и Y координаты точки , например WRITE(X[1];Y[1]) - на экране координаты первой точки 1 1

Глава #2 «Площадь треугольника»

*от урока к олимпиаде*

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

Представим такую задачу «Найти площадь треугольника , с точностью до третьего знака после запятой, заданного координатами своих точек в порядке обхода.».

Пример:                                                                                                                          

INPUT.TXT

 3

0 0

0 1

1 1

OUTPUT.TXT

 0.500

Здесь нам для вывода площади придется использовать вещественный тип, который в Паскале задается как REAL, введем переменную для площади S:real;

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

X1                   Y1

X2                   Y2

X3                   Y3

X1                   Y1

Составим разность между суммой произведений указанных стрелками и возьмем абсолютное значение ее половины , у вас площадь треугольника!

S:=abs(xl ×y2+x2×y3+x3×yl-(yl×x2+y2×y3+y3×xl))/2

Полный текст программы:

var      i: integer;

n: integer;

x,y:array[1..100] of integer;

s:real;

 begin

assign(input,'input.txt');

        assign(output,'output.txt');

 reset(input);

        rewrite(output);

 read(n);

for i: = l to n do read(x[i],y[i]);

s:=abs(x[l]*y[2]+x[2]*y[3]+x[3]*y[l]-(y[l]*x[2]+y[2]*x[3]+y[3]*x[l]))/2;

write(s:3:3);

 end.

Практическое задание:

l.Ha диске А создать файл PLO.PAS и ввести программу

2.Во входной файл INPUT.TXT записать количество точек и координаты этих

точек в виде таблицы:

INPUT.TXT

3

0 0

0 1

1 1

OUTPUT.TXT

0.500

3.Протестировать программу на

INPUT.TXT

3

0 0

2 2

2 О

OUTPUT.TXT

0.200                                                                                                               

проверить результат вручную в XOY ( тетрадь в клетку )          

Глава #3 «Вопросы для повторения и ДЗ»

Вопросы для повторения:

1.   Как описываются координаты точек в Паскале?

2.   Какая формула вычисляет площадь треугольника, заданного координатами своих точек?

Домашнее задание:

Написать программу «Найти длину отрезка, заданного координатами своих точек»

Пример:

INPUT.TXT

2

0 0

1 1

OUTPUT.TXT

0.707