Вычислительная геометрия (стр. 2 )

SAB = (X1 - X2) * (Y1 + Y2) / 2

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

Площадь всего многоугольника получается суммированием по всем сторонам при последовательном обходе в определенном направлении, то есть

S = S(1, 2) + S(2, 3) +…+ S(N, 1),

где S(i, j) – площадь со знаком трапеции, соответствующей очередной стороне многоугольника. Действительно, если считать для наглядности, что многоугольник расположен выше оси X и обход производится по часовой стрелке, то “лишняя” площадь под нижними сторонами многоугольника вычитается при их обходе. Если порядок обхода вершин неизвестен, нужно снова взять полученное значение по модулю.

Приведем текст программы.

Program Poligon;

Const

Max=1000;

Eps=0.00001;

Type

Para=record

X: integer;

Y: integer;

end;

ArrPara=array [1..Max] of Para;

Var

M, N,i, j,k, T,R: integer;

A, H1: ArrPara;

{A-начальные координаты точек, H1-углов многоугольников}

P, S: real; {периметр и площадь}

Fin, Fout: text; {входной и выходной файлы}

F: boolean;

Procedure Oboloch(Var H:ArrPara; R:integer; var T:integer);

{R-количество исходных точек, T-точек оболочки}

Var

ii, jj, i,j: integer;

S, C,Z, E: real;

V1,V2,V3,V4: real;

D1,D2,D3,D4: integer;

Begin

S:=A[1].Y;

j:=1; {номер самой левой из нижних точек}

For i:=1 to R do

if (A[i].Y<S) or ((A[i].Y=S) and (A[i].X<A[j].X)) then

begin

j:=i;

S:=A[i].Y

end;

D1:=-1; D2:=0;

H[1].X:=A[j].X; {первая вершина оболочки}

H[1].Y:=A[j].Y; T:=1;

jj:=j;

S:=-2;

{для поиска минимального угла (максимального косинуса) между

вектором (D1, D2) и вектором (A[i].X)-A[j].X, A[i].Y-A[j].Y) }

E:=-1;

{для поиска наиболее удаленной точки среди всех с

минимальным углом}

Repeat

For i:=1 to R do

begin

D3:=A[i].X-A[j].X;

D4:=A[i].Y-A[j].Y;

V1:=D1; V2:=D2; V3:=D3; V4:=D4;

Z:=Sqrt(V3*V3+V4*V4);

if (i=j) or ((D3=0) and (D4=0)) then {пропускаем точку}

else

begin

C:=(V1*V3+V2*V4)/(Sqrt(V1*V1+V2*V2)*Sqrt(V3*V3+V4*V4));

if (C>S) or ((Abs(C-S)<Eps) and (Z>E)) then

begin

ii:=i;

S:=C;

E:=Z;

end;

end;

end;

if ii<>jj then

begin

D1:=A[ii].X-A[j].X; {вектор стороны оболочки}

D2:=A[ii].Y-A[j].Y;

T:=T+1;

H[T].X:=A[ii].X; {следующая вершина оболочки}

H[T].Y:=A[ii].Y;

S:=-2; E:=-1;

end;

j:=ii;

Until j=jj; {пока не придем в начальную точку}

End;

Function Perim(Var H:ArrPara; L:integer): real;

{периметр многоугольника, L-число вершин}

Var

P: real;

i: integer;

V1,V2: real;

Begin

P:=0;

H[L+1]:=H[1];

For i:=1 to L do

begin

V1:=H[i+1].X-H[i].X;

V2:=H[i+1].Y-H[i].Y;

P:=P+Sqrt(V1*V1+V2*V2);

end;

Perim:=P;

End;

Function Squ(Var H:ArrPara; L:integer): real;

{площадь многоугольника, L-число вершин}

Var

S: real;

i: integer;

V1,V2,V3,V4: real;

Begin

S:=0;

H[L+1]:=H[1];

For i:=1 to L do

begin

V1:=H[i+1].Y+H[i].Y;

V2:=H[i+1].X-H[i].X;

S:=S+V1*V2/2;

end;

Squ:=Abs(S);

End;

Begin

Assign(Fin,'input. txt');

Reset(Fin);

ReadLn(Fin, N); {количество точек}

For i:=1 to N do

ReadLn(Fin, A[i].X, A[i].Y); {координаты точек}

Close(Fin);

Oboloch(H1,N, T);

P:=Perim(H1,T); {периметр}

S:=Squ(H1,T); {площадь}

Assign(Fout,'output. txt');

Rewrite(Fout);

WriteLn(Fout, P:10:1);

WriteLn(Fout, S:10:1);

Close(Fout);

End.

Задачи для самостоятельного решения

11.1. Треугольник и точка (5)

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

Ввод из файла INPUT. TXT. В четырех строках находятся пары чисел - координаты точек. Числа в первых трех строках - это координаты вершин треугольника, в четвертой строке - координаты тестируемой точки.

Вывод в файл OUTPUT. TXT. Вывести In, если точка находится внутри треугольника, или Out - если снаружи.

Ограничения: координаты вершин - целые числа, для любой точки выполняются следующие условия: -109 ≤ x, y ≤ 109, время 1 с.

Примеры

Ввод 1 Ввод 2 Ввод 3 Ввод 4

0 0 0 0 0 0 0 0

100 0 100 0 100 0 100 0

0 100 0 100 0 100 0 100

100 100 10 10 50 50 0 0

Вывод 1 Вывод 2 Вывод 3 Вывод 4

Out In In In

11.2. Левые повороты (4)

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

Ввод. Первая строка состоит из одного числа N (3 £ N £ 1000), количества вершин ломаной. В последующих строках - пары натуральных чисел (Xi, Yi), координаты вершин ломаной (-104 £ Xi, Yi £ 104).

Вывод. Выходной файл содержит одно число - количество левых поворотов.

Пример

Ввод

4
1 1
2 2
3 2
3 5
Вывод

1

11.3. Даешь квадрат (5)

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

Ввод из файла INPUT. TXT. В первой строке находится число M, задающее количество вершин первого многоугольника. Следующие M строк содержат пары целых чисел - координаты точек (Xi, Yi). Если соединить точки в данном порядке, а также первую и последнюю точки, то получится первый многоугольник. Далее аналогично указываются число N – количество вершин второго многоугольника и N строк с координатами его вершин. Таким образом, тест занимает M + N + 2 строк. Начальная вершина и направление обхода вершин каждого многоугольника могут быть произвольными.

Вывод в файл OUTPUT. TXT. Выводится единственная строка со значением Yes или No – является четырехугольник квадратом или нет.

Ограничения: 3 ≤ M, N ≤ 1000; -100 ≤ Xi, Yi ≤ 100; время 1 с.

Примеры

Ввод 1 Ввод 2

6 8

0 0 0 0

0 1 0 6

1 1 5 5

1 2 5 0

2 2 3 0

2 0 4 1

4 1 1

0 2 2 0

1 2 4

1 1 1 1

0 1 2 0

3 0

4 1

Вывод 1 Вывод 2

Yes No

11.4. Стена (6)

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

Ваша задача - помочь Архитектору сохранить голову, написав программу, определяющую минимальную длину стены, которую можно построить вокруг замка, удовлетворив требования Короля.

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

Ввод из файла INPUT. TXT. Первая строка содержит два целых числа N и L, разделённых пробелом: N - число углов в замке Короля, а L - минимальное число футов, на которое Король разрешил приблизить стену к замку.

Следующие N строк описывают координаты углов замка в порядке обхода по часовой стрелке. Каждая строка содержит два целых числа xi и yi, разделённых пробелом и представляющих собой координаты i-го угла в футах. Все углы имеют различные координаты, и стены замка не пересекаются иначе как в углах.

Ограничения: 3 ≤  N ≤ 1000, 1 ≤  L ≤ 1000, -10000 ≤  xi, yi ≤ 10000, время 2 с.

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

Пример

Ввод

9 100

200 400

300 400

300 300

400 300

400 400

500 400

500 200

350 200

200 200

Вывод

1628

11.5. Клад (6)

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

Ввод из файла INPUT. TXT. В первой строке находится число N, задающее количество вершин ломаной. Следующие N строк содержат пары целых чисел - координаты вершин (Xi, Yi). Ломаная получается путем последовательного соединения точек в данном порядке. Направление обхода вершин ломаной может быть произвольным. Точки (X1 , Y1) и (XN , YN) лежат на одной или разных сторонах квадрата, остальные точки ломаной – внутри квадрата.