Взамное расположение точки и прямой

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

Function pr(x, y, x1, y1, x2, y2:longint):longint;

{взаимное расположение точки и прямой}

Begin

pr:=(x-x1)*(y2-y1)-(x2-x1)*(y-y1)

End;

Var x, y, x1, y1, x2, y2, p: longint;

Begin

x1:=0; y1:=0; x2:=4; y2:=4;

Readln(x, y);

p:=pr(x, y, x1, y1, x2, y2);

If p<0 then Write('L')

else if p>0 then Write('p')

   else Write('0');

Readln

End.

Площадь многоугольника

Известная из школьной программы формула Герона вычисляет площадь треугольника по длинам сторон треугольника (L1, L2, L3).

            S=

где P=(L1+L2+L3)/2- полупериметр треугольника.

В задачах, где треугольник задан координатами вершин, проще использовать формулу ориентированной площади треугольника[5].

Пусть вершины треугольника имеют коодинаты (x1, y1), (x2, y2) и (x3, y3). Ориентированная площадь равна площади треугольника, но имеет знак. Знак площади зависит от порядка обхода вершин, при обходе против часовой стрелки знак положительный, по часовой отрицательный.

 

 

 

Ориентированная площадь треугольника – это его обычная площадь, только со знаком. Знак у ориентированной площади треугольника ABC такой же, как у ориентированного угла между векторами  и , то есть ее знак зависит от порядка перечисления вершин. На рис.4 треугольник ABC прямоугольный. Его ориентированная площадь равна ( * )/2. Эту же величину можно вычислить другим способом. Площадь треугольника ABC получится, если из площади треугольника OBC вычесть площади треугольников OAB и OCA. Таким образом, нужно просто сложить ориентированные площади треугольников OAB, OBC и OCA.

Аналогично можно вычислить площадь любого многоугольника, не обязательно выпуклого. Нужно просто сложить ориентированные площади треугольников, одна вершина которых - (0, 0), а две другие - соседние вершины многоугольника. Ориентированная площадь параллелограмма построенного на векторах a=(X₁, Y₁) и b=(X₂, Y₂) равна 2S=X₁*Y₂-X₂*Y₁, где S ориентированная площадь треугольника.

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

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

Const nmax=100;

var

x, y: array[1..nmax] of real;

i, n: integer;

s: real;

begin

Read(n);

For i:=1 to n do Read(x[i], y[i]);

s:= 0.0;

for i:= 1 to n-1 do begin

s:=s+ (x[i] * y[i+1]-x[i+1] * y[i]);

end;

s:=s+x[n]*y[1]-x[1]*y[n];{от последней к первой}

s:= abs(s)*0.5;

Write(s:0:3);

end.

Выпуклая оболочка

Для конечного множества точек выпуклой оболочкой всегда будет выпуклый многоугольник, все вершины которого есть точки этого множества, а все остальные точки множества оказываются внутри или на сторонах этого многоугольника. Наша задача найти вершины выпуклой оболочки среди заданного множества точек. Будем перечислять точки в порядке их обхода против часовой стрелки. Наиболее простым является алгоритм Джарвиса. Перечисление точек начнем с правой нижней точки P1. Следующей точкой оболочки будет точка P2, при выборе которой все остальные точки лежат слева от вектора  (функции vect). Очевидно, что для выбора очередной точки нужно проверять на это условие все множество точек. Если подходящих точек несколько, то выбираем точку, для которой длина вектора  максимальна (функция dist). Выбранные точки записываются в массив b. Приведенная программа целиком заимствована из работы [5].

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

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

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

Если вы не знакомы с типом Record, то следует читать [1] или удовлетвориться нашим кратким пояснением. Запись (Record) это структура данных, состоящая из фиксированного числа компонент (полей). В отличие от массива компоненты могут быть различных типов. Для ссылки поля именуются. Например, в программе поле xв массиве a, будет доступно по имени a[i].x, а поле y по имени a[i].y. В предыдущих примерах мы использовали для координат точек два массива.

Type vv=Record

    x, y:longint;

   End;

Var a, b: array[1..101] of vv;

min, m, i, j, k, n:integer;

Function vect(a1, a2, b1, b2: vv):longint;

{косое произведение векторов а1а2 и в1в2}

Begin

vect:=(a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y)

End;

Function dist2(a1, a2:vv): longint;

{квадрат длины вектора}

Begin

dist2:=sqr(a2.x-a1.x)+sqr(a2.y-a1.y)

End;

Begin

Readln (n); { количество точек}

For i:=1 to n do Read (a[i].x, a[i].y);

{ ищем правую нижнюю точку}

m:=1;

For i:=2 to n do

if a[i].y<a[m].y then m:=i

else

  if (a[i].y = a[m].y) and

     (a[i].x > a[m].x) then m:=i;

{запишем ее в массив выпуклой оболочки «в»}

b[1]:=a[m];

{и переставим на первое место в исходном массиве}

a[m]:=a[1];

a[1]:=b[1];

k:=1;

min:=2;

repeat

{ищем очередную вершину выпуклой облочки}

For j:=2 to n do

if (vect (b[k],a[min],b[k], a[j])<0) or

  ((vect (b[k],a[min],b[k], a[j])=0) and

  (dist2 (b[k], a[min])< dist2(b[k], a[j])))

then min:=j;

k:=k+1;

{записана очередная вершина}

b[k]:=a[min];

min:=1;

until (b[k].x=b[1].x) and (b[k].y=b[1].y);

{пока ломаная не замкнется}

 For j:=1 to k-1 do

Writeln(b[j].x, ' ',b[j].y);

 readln

end.

Алгоритмы на графах

Алгоритм Флойда

Наиболее просто найти кратчайший путь между каждой из пар вершин можно с помощью алгоритма Флойда. Пусть в элементе матрицы A[i, j] хранится длина пути из вершины i в вершину j. Если же длины пути из вершины i в вершину k и пути из вершины k в вершину j таковы, что их сумма меньше, чем значение данного элемента матрицы, то его следует переопределить. Для реализации алгоритма массив A первоначально следует заполнить элементами матрицы весов, обозначая отсутствие ребра между двумя вершинами “бесконечностью” — числом, заведомо превосходящим длину любого пути в рассматриваемом графе, но меньшим, чем максимальное значение используемого типа данных, чтобы было возможно выполнять с ним арифметические операции.

Const nmax=25;

Var a:array[1..nmax,1..nmax] of real;

  i, j, k, n: integer;

  f, f1: text;

Begin

Assign (f, '1.txt'); reset(f);

Readln (f, n);

For i:=1 to n do Begin

For j:=1 to n do Read(f, a[i,j]);

Readln (f);

End;

For k:= 1 to n do

For i:= 1 to n do

   For j:= 1 to n do

     If a [i, j]>a[i, k]+a[k, j] then a[i, j]:= a[i, k]+a[k, j];

Assign (f1, '2.txt'); Rewrite (f1);

For i:=1 to 5 do Begin

For j:=1 to 5 do Write(f1,a[i,j]:4:0,' ');

Writeln(f1);

End;

Close(f1);

End.

В этом решении в исходной матрице весов будут записаны кратчайшие пути между всеми вершинами.

На соревнованиях в условии задачи вряд ли будет дана матрица весов. Там будет, например, как в задаче «На болоте», она приведена в задачах олимпиад.

Если же нам требуется найти сам кратчайший путь, а не его длину, то при каждом улучшении пути между двумя вершинами мы в соответствующем элементе вспомогательного массива (в программе — w) будем запоминать номер той вершины, через которую кратчайший путь проходит, а затем с помощью рекурсивной процедуры будем его печатать. Идея рекурсии заключается в том, что если мы знаем, что кратчайший путь от вершины i до вершины j проходит через вершину k, то мы можем обратиться к той же самой процедуре с частями пути от i до k и от k до j. Выход из рекурсии, когда на кратчайшем пути между двумя вершинами не окажется промежуточных вершин.

Приведем фрагмент программы, реализующий алгоритм Флойда и печатающий кратчайшие пути между всеми парами вершин графа.

Procedure Way(i,j:integer);

{печатает путь между вершинами i и j}

Begin

If w[i,j]=0 then Write (' ', j)

{печатаем только вершину j, чтобы избежать повторов}

else

  Begin

Way (i, w [i, j]); Way (w [i, j], j)

 End

End;

Begin

 …{заполняем матрицу смежности}

… {реализуем алгоритм Флойда }

For k:=1 to nn do

  For i:=1 to nn do

   For j:=1 to nn do

    If a[i,k]+a[k,j]<a[i,j] then

     Begin

       a[i,j]:=a[i,k]+a[k,j];

      w[i,j]:=k

      End;

{выводим кратчайшие пути}

  For i:=1 to nn do

For j:=1 to nn do Begin

  Write(i);

   If i<>j then Way(i,j);

  Writeln

  End

End.

Алгоритм Флойда прост и хорошо запоминается. Но упростить его для определения длины кратчайшего пути между двумя конкретными вершинами невозможно. Для решения такой задачи используйте алгоритм Дейкстры (п. 13.1.3).

Задачи олимпиад

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

В будущем Вам придется изучить комбинаторику, теорию графов, динамическое программирование, численные методы. А пока решайте задачи на сайтах ACM.TIMUS.RU, ACM.SGU.RU и CONTEST.SAMARA.RU.

Внимательно читайте условия задачи, сторого соблюдайте форматы входных и выходных данных. Помните, что даже лишний пробел в выходных данных может стать причиной ошибки. Обязательно тестируйте свою программу не только на тестах, приведенных в условиях задачи, но и на собственных тестах, как можно более «вредных». При тестировании используйте текстовые файлы, даже если тестирующая программа не требует явного использования файлов. Так, например, сайты ACM.TIMUS.RU и ACM.SGU.RU не требуют явного использования файлов, а сайт CONTEST.SAMARA.RU пока требует. Но при автоматическом тестировании на сайте файлы, конечно, использоваться будут.