В выпуклом четырехугольнике каждые две противоположные вершины лежат по разные стороны относительно диагонали, соединяющей две другие вершины. Если же четырехугольник не является выпуклым, то относительно одной из диагоналей две вершины находятся по одну сторону. Если вывести уравнение диагонали по двум точкам в виде AX + BY +C = 0 (в частных случаях A = 0 или B = 0), то выражение Z = AX + BY +C обращается в 0 на диагонали и имеет разные знаки в точках по разные стороны диагонали. Остается для каждого четырехугольника вывести уравнения диагоналей и проверить для обеих диагоналей указанные условия, подставляя координаты вершин в выражение для Z.

Приведем текст программы для решения этой несложной задачи.

Const Max=100;

Var

L,i,j: integer;

X: array[1..4] of integer;

Y: array[1..4] of integer;

A,B,C: longint;

Fin,Fout: text;

Znak1,Znak2:integer;

Znak3,Znak4:integer;

Function WhatZnak(X1,Y1,X2,Y2,X,Y: integer):integer;

{возвращает знак при подстановке (X,Y) в уравнение прямой,

проходящей через точки (X1,Y1) и (X2,Y2):

1-больше 0, -1-меньше, 0-равно;

уравнение прямой через точки (X1,Y1) и (X2,Y2):

(Y2-Y1)*X+(X1-X2)*Y+X1(Y1-Y2)+Y1*(X2-X1)=0 }

Var

A,B,C,V: longint;

Begin

A:=Y2-Y1; B:=X1-X2;

C:=X1*(Y1-Y2)+Y1*(X2-X1);

V:=A*X+B*Y+C;

if V>0 then WhatZnak:=1

else if V<0 then WhatZnak:=-1

else WhatZnak:=0

End;

Begin

Assign(Fin,'input.txt');

Reset(Fin);

Assign(Fout,'output.txt');

Rewrite(Fout);

ReadLn(Fin,L); {число тестовых блоков}

For i:=1 to L do

begin

For j:=1 to 4 do ReadLn(Fin,X[j],Y[j]);

Znak2:=WhatZnak(X[1],Y[1],X[3],Y[3],X[2],Y[2]);

{знак второй вершины отоносительно первой диагонали}

Znak4:=WhatZnak(X[1],Y[1],X[3],Y[3],X[4],Y[4]);

{знак четвертой вершины отоносительно первой диагонали}

Znak1:=WhatZnak(X[2],Y[2],X[4],Y[4],X[1],Y[1]);

{знак первой вершины отоносительно второй диагонали}

Znak3:=WhatZnak(X[2],Y[2],X[4],Y[4],X[3],Y[3]);

{знак третьей вершины отоносительно второй диагонали}

if (Znak2=Znak4) or (Znak1=Znak3) then

WriteLn(Fout,'No') {невыпуклый}

else

WriteLn(Fout,'Yes') {выпуклый}

end;

Close(Fin);

Close(Fout);

End.

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

Ввод из файла INPUT.TXT. В первой строке находится число N, далее - N строк с парами координат.

Вывод в файл OUTPUT.TXT. Вывести с одним знаком после запятой: в первой строке - длину периметра, во второй - площадь.

Ограничения: 3 ≤ N ≤ 1000, -1000 ≤ x_i, y_i ≤ 1000, все числа целые, все точки различны, время 2 с.

Пример

Ввод

5

1 0

0 1

-1 0

0 -1

0 0

Вывод

5.7

2.0

Опишем алгоритм Джарвиса как наиболее известный способ построения выпуклой оболочки [2-4, 6]. Сначала находится первая вершина многоугольника. Например, из множества самых нижних вершин выбирается самая левая. Найдем другие вершины в порядке обхода точек по часовой стрелке, предполагая сначала, что все точки различны.

Возьмем вектор (-1, 0) и обозначим его как (d₁, d₂). Вторая вершина выбирается так, чтобы угол между вектором (d₁, d₂) и вектором из первой вершины во вторую был минимален. Можно сказать, что вторая точка получается минимальным поворотом вектора (d₁, d₂) из первой точки по часовой стрелке. Если таких точек несколько, то возьмем наиболее удаленную из них.

Далее вектором (d₁, d₂) будем считать вектор из первой точки во вторую и будем находить следующую точку и т. д. Все продолжается, пока снова не придем в первую точку.

Минимальный угол можно найти с помощью скалярного произведения векторов. Ему соответствует максимальное значение косинуса, изменяющегося от -1 до 1. Поскольку некоторые точки могут повторяться, при поиске следующей вершины многоугольника не нужно исследовать точки, совпадающие с текущей вершиной.

Трудоемкость этого алгоритма O(N²), где N – количество точек. Иногда его называют алгоритмом обертки. Действительно, можно представить, что точки на плоскости соответствуют вбитым гвоздикам, вокруг которых натягивают ленту. Есть более быстрый алгоритм Грэхема [3, 4, 6], трудоемкость которого O(N logN).

Снова из множества самых нижних вершин выбирается самая левая. Обозначим ее A₀. Точка A₀ заведомо принадлежит выпуклой оболочке. В нее переносится центр координат. Остальные вершины сортируются одним из методов быстрой сортировки по возрастанию полярного угла. Если несколько точек имеют одинаковый угол, то оставляется одна с максимальным радиус-вектором. Обозначим оставшиеся точки A₁, A₂, …, A_M в соответствии с порядком сортировки. Будем последовательно, т.е. в направлении против часовой стрелки рассматривать тройки точек A_k-1, A_k, A_k+1. С помощью векторного произведения найдем ориентированную площадь треугольника A_k-1A_kA_k+1. По знаку площади можно определить, находится ли точка A_k внутри треугольника A₀A_k-1A_k+1. Если это так, то точка A_k исключается. Сейчас уже точка A_k-1 может находиться внутри треугольника A₀A_k-2A_k+1. Как только исключение промежуточных точек завершается, можно перейти к следующему значению k. По окончанию обхода оставшиеся точки будут углами многоугольника, являющегося выпуклой оболочкой.

Найдем площадь многоугольника. Пусть даны две точки A(X₁,Y₁) и B(X₂,Y₂). Площадь S трапеции, образованной отрезком AB, определяется как

S_AB = (X₁ - X₂) * (Y₁ + Y₂) / 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 - если снаружи.

Ограничения: координаты вершин - целые числа, для любой точки выполняются следующие условия: -10000 <= x, y <= 10000, время 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), количества звеньев ломаной. В последующих строках - пары натуральных чисел (X_i, Y_i), координаты вершин ломаной (-10⁴  X_i, Y_i  10⁴).

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

Пример

Ввод

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

1