11. Вычислительная геометрия
Вычислительная геометрия – один из разделов информатики. Существует большое количество научных и прикладных задач, связанных с вычислительной геометрией.
Рассмотрим сначала типы данных, применяемых для вычислений. Точка на плоскости описывается парой вещественных чисел. При использовании вещественного типа операции сравнения лучше всего оформить специальными функциями, то есть сравнения вида A=B, где A и B вещественные числа, использовать не стоит. Приведем пример [4].
Пусть для хранения вещественного типа используются два десятичных разряда для порядка и шесть разрядов для хранения мантиссы. Есть два числа: A=0.34567´104 и B=0.98765´10-4. При сложении и вычитании происходит выравнивание порядков, сложение (вычитание) мантисс и нормализация результата. После выравнивания порядков получим B=0.0000000098765´104, а после сложения мантисс и будет результат:
A+B = 0. 3456700098765
При шести десятичных разрядах мантиссы после округления окажется, что A+B=A при B>0! В реальных системах тоже есть подобные ограничения на разрядность представления вещественного типа данных. Например, для типа Real в ПАСКАЛе мантиссе отводится 11-12 цифр.
Операцию проверки равенства вещественных чисел можно реализовать следующей функцией:
Function IsEqual(A, B: real): boolean;
Begin
IsEqual:=Abs(A-B)<Eps
{ Eps – константа, определяющая точность, например Eps=1e-10 }
End;
Операцию проверки “больше или равно” можно реализовать так:
Function IsMoreEqual(A, B: real): boolean;
Begin
IsMoreEqual:=(A>B) or Abs(A-B)<Eps
End;
Остальные функции сравнения пишутся аналогично. Эти функции можно использовать, например, для определения максимального из двух значений.
Во многих задачах используются векторное и скалярное произведения векторов. Пусть, например, треугольник ABC задан координатами точек A(X1,Y1), B(X2,Y2), C(X3,Y3). Требуется:
· найти площадь треугольника;
· определить значение Cos A.
Вектора сторон имеют координаты AB (X2 - X1, Y2 - Y1) и AC (X3 - X1, Y3 - Y1). Ориентированная площадь треугольника проще всего находится через векторное произведение, обозначенное символом ‘´ ’:
S = (AB ´ AC) / 2 = ((X2 - X1 )* (Y3 - Y1 ) - (X3 - X1 )* (Y2 - Y1 )) / 2
Ориентация определяется знаком величины S.
Значение Cos A определяется из скалярного произведения векторов AB и AC:
Cos A =((X2 - X1 )* (Y3 - X1 )+ (X2 - X1 )* (Y3 - X1 )) / ( | AB | * | AC | )
Угол B прямой, если числитель (скалярное произведение) обращается в ноль.
Рассмотрим следующую задачу.
Четырехугольник. Заданы координаты четырех вершин четырехугольника в порядке обхода по часовой стрелке. Совпадающих вершин нет. Требуется определить, является ли четырехугольник выпуклым.
Ввод из файла INPUT. TXT. Первая строка содержит число тестовых блоков L (L ≤ 10). Каждый тестовый блок состоит из четырех строк, задающих координаты вершин четырехугольника в виде двух целых чисел X и Y (-1000 ≤ X, Y ≤1000), разделенных пробелом.
Вывод в файл OUTPUT. TXT. Для каждого тестового блока выводится единственная строка со значением Yes или No – является четырехугольник выпуклым или нет.
Пример
Ввод
2
0 0
-1 2
3 5
7 -1
1 0
0 5
5 0
2 1
Вывод
Yes
No
В выпуклом четырехугольнике каждые две противоположные вершины лежат по разные стороны относительно диагонали, соединяющей две другие вершины. Если же четырехугольник не является выпуклым, то относительно одной из диагоналей две вершины находятся по одну сторону. Если вывести уравнение диагонали по двум точкам в виде AX + BY +C = 0 (в частных случаях A = 0 или B = 0), то выражение Z = AX + BY +C обращается в 0 на диагонали и имеет разные знаки в точках по разные стороны диагонали. Остается для каждого четырехугольника вывести уравнения диагоналей и проверить для обеих диагоналей указанные условия, подставляя координаты вершин в выражение для Z.
Приведем текст программы для решения этой несложной задачи.
Program FourAng;
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.
Рассмотрим еще одну базовую задачу вычислительной геометрии [2].
Выпуклая оболочка. На плоскости заданы своими декартовыми координатами N точек. Найти минимальный периметр многоугольника, содержащего все эти точки. Определить площадь этого многоугольника. Гарантируется, что искомый многоугольник имеет ненулевую площадь.
Ввод из файла INPUT. TXT. В первой строке находится число N, далее - N строк с парами координат.
Вывод в файл OUTPUT. TXT. Вывести с одним знаком после запятой: в первой строке - длину периметра, во второй - площадь.
Ограничения: 3 ≤ N ≤ 1000, -1000 ≤ xi, yi ≤ 1000, все числа целые, все точки различны, время 2 с.
Пример
Ввод
5
1 0
0 1
-1 0
0 -1
0 0
Вывод
5.7
2.0
Во-первых, искомый многоугольник должен быть выпуклым. Во-вторых, вершины многоугольника должны совпадать с какими-то из заданных точек. Оба эти свойства доказываются от противного. Данный многоугольник называется выпуклой оболочкой множества точек.
Опишем алгоритм Джарвиса как наиболее известный способ построения выпуклой оболочки [2-4, 6]. Сначала находится первая вершина многоугольника. Например, из множества самых нижних вершин выбирается самая левая. Найдем другие вершины в порядке обхода точек по часовой стрелке, предполагая сначала, что все точки различны.
Возьмем вектор (-1, 0) и обозначим его как (d1, d2). Вторая вершина выбирается так, чтобы угол между вектором (d1, d2) и вектором из первой вершины во вторую был минимален. Можно сказать, что вторая точка получается минимальным поворотом вектора (d1, d2) из первой точки по часовой стрелке. Если таких точек несколько, то возьмем наиболее удаленную из них.
Далее вектором (d1, d2) будем считать вектор из первой точки во вторую и будем находить следующую точку и т. д. Все продолжается, пока снова не придем в первую точку.
Минимальный угол можно найти с помощью скалярного произведения векторов. Ему соответствует максимальное значение косинуса, изменяющегося от -1 до 1. Поскольку некоторые точки могут повторяться, при поиске следующей вершины многоугольника не нужно исследовать точки, совпадающие с текущей вершиной.
Трудоемкость этого алгоритма O(N2), где N – количество точек. Иногда его называют алгоритмом обертки. Действительно, можно представить, что точки на плоскости соответствуют вбитым гвоздикам, вокруг которых натягивают ленту. Есть более быстрый алгоритм Грэхема [3, 4, 6], трудоемкость которого O(N´ logN).
Снова из множества самых нижних вершин выбирается самая левая. Обозначим ее A0. Точка A0 заведомо принадлежит выпуклой оболочке. В нее переносится центр координат. Остальные вершины сортируются одним из методов быстрой сортировки по возрастанию полярного угла. Если несколько точек имеют одинаковый угол, то оставляется одна с максимальным радиус-вектором. Обозначим оставшиеся точки A1, A2, …, AM в соответствии с порядком сортировки. Будем последовательно, т. е. в направлении против часовой стрелки рассматривать тройки точек Ak-1, Ak, Ak+1. С помощью векторного произведения найдем ориентированную площадь треугольника Ak-1AkAk+1. По знаку площади можно определить, находится ли точка Ak внутри треугольника A0Ak-1Ak+1. Если это так, то точка Ak исключается. Это не означает, что предыдущая не исключенная точка Ak-1 входит в выпуклую оболочку. Точка Ak-1 может находиться внутри треугольника A0Ak-2Ak+1, что приведет к ее исключению. Для возврата к предыдущим точкам можно использовать стек. Как только исключение промежуточных точек завершается, можно перейти к следующей еще не рассмотренной точке. По окончанию обхода оставшиеся точки будут углами многоугольника, являющегося выпуклой оболочкой.
Найдем площадь многоугольника. Пусть даны две точки A(X1,Y1) и B(X2,Y2). Площадь S трапеции, образованной отрезком AB, определяется как
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 3
Вывод
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) лежат на одной или разных сторонах квадрата, остальные точки ломаной – внутри квадрата.
Ограничения: 3 ≤ N ≤ 100; -100 ≤ Xi ≤ 100; -100 ≤ Yi ≤ 100; время работы программы до 2 сек.
Вывод в файл OUTPUT. TXT. Выводится единственная строка со значением Yes или No – возможность либо невозможность разъединения квадрата путем перемещения его частей по плоскости без вращений.
Примеры
Ввод 1 Ввод 2
5 4
0 0 3 0
0 1 4 1
1 1 1 1
2 2 2 0
2 0
Вывод 1 Вывод 2
Yes No
Подсказка. Если разъединение существует, то его можно добиться перемещением какой-либо плиты в направлении одной из звеньев ломаной разреза.
11.6. Треугольники (6)
Роман достаточно давно занимается в математическом кружке, поэтому он уже успел узнать не только правила выполнения простейших операций, но и о таком достаточно сложном понятии как симметрия. Для того чтобы получше изучить симметрию, Роман решил начать с наиболее простых геометрических фигур – треугольников. Он скоро понял, что осевой симметрией обладают так называемые равнобедренные треугольники. Напомним, что треугольник называется равнобедренным, если его площадь положительна, и у него есть хотя бы две равные стороны.
Недавно Роман, зайдя в класс, увидел, что на доске нарисовано n точек. Разумеется, он сразу задумался, сколько существует троек из этих точек, которые являются вершинами равнобедренных треугольников.
Требуется написать программу, решающую указанную задачу.
Ввод из файла INPUT. TXT. В первой строке целое число n (3 ≤ n ≤ 1500). Каждая из последующих строк содержит по два разделенных пробелом целых числа – xi и yi , определяющих координаты i-ой точки. Все координаты точек не превосходят 109 по абсолютной величине. Среди заданных точек нет совпадающих.
Вывод в файл OUTPUT. TXT. В единственной строке необходимо вывести ответ.
Примеры
Ввод 1 Ввод 2
3 4
0 0 0 0
2 2 1 1
-2 2 1 0
0 1
Вывод 1 Вывод 2
1 4
Подсказка. Составим массив с длинами всех расстояний между точками. Для каждого элемента массива будем сохранять номера начальной и конечной точек. Таким образом, каждое ребро между двумя точками войдет в массив дважды. Для каждого ребра рассчитаем дополнительно угол наклона - против часовой стрелки от положительного направления оси X (значение от 0 до 2π).
Проведем быструю сортировку массива ребер в первую очередь по номеру начальной точки ребра, далее по их длине, а при одной и той же начальной точке и равных длинах по углу наклона.
Организуем просмотр отсортированного списка ребер. Два ребра могут быть сторонами очередного равнобедренного треугольника при выполнении следующих условий:
· ребра выходят из одной и той же вершины;
· ребра имеют равную длину;
· ребра не лежат на одной прямой, то есть образуют треугольник ненулевой площади;
Если некоторый треугольник равносторонний, то он будет посчитан 3 раза по каждой из своих вершин. Проще всего учитывать в процессе перебора количество равносторонних треугольников, чтобы в конце сделать необходимую поправку.
11.7. Гомотетия (6)
Гомотетией с центром O и коэффициентом k ¹ 0 называют преобразование плоскости, при котором точка O переходит сама в себя, а любая точка X ¹ O – в такую точку Y, что:
· Y лежит на прямой OX;
· OY = |k|OX;
· при k >0 Y лежит на луче OX, при k <0 Y лежит на продолжении луча OX за точку O.
Требуется написать программу, которая по координатам вершин двух различных простых N-угольников определяет, существует ли гомотетия, переводящая первый многоугольник во второй и, если существует, вычисляет ее центр и коэффициент.
Ввод из файла INPUT. TXT. В первой строке входного файла содержится целое число n (3 ≤ n ≤ 1000) – количество вершин в каждом многоугольнике. В следующих n строках – по два целых числа x и y (-106 ≤ x, y ≤ 106) – координаты вершин первого многоугольника в порядке обхода против часовой стрелки. В следующих n строках – по два целых числа x и y (-106 ≤ x,y ≤ 106) – координаты вершин второго многоугольника в порядке обхода против часовой стрелки.
Вывод в файл OUTPUT. TXT. Если существует гомотетия, которая переводит первый многоугольник во второй, то необходимо вывести в первой строке выходного файла слово «YES», а во второй строке – три пары вещественных чисел – координаты центра гомотетии и ее коэффициент, которые вычисляются с точностью не менее 10-5. Если искомой гомотетии не существует, необходимо вывести в выходной файл слово «NO».
Примеры
Ввод 1 Ввод 2
3 3
-1 1 -1 1
1 1 1 1
1 5 1 5
1 9 1 1
-3 1 0 0
1 1 1 0
Вывод 1 Вывод 2
YES NO
1 0 1 0 2 0
11.8. Пересечение отрезков (5)
Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат. Требуется определить, существует ли у них общая точка.
Ввод из файла INPUT. TXT. В первой строке содержатся координаты первого конца первого отрезка, во второй - второго конца первого отрезка, в третьей и четвёртой - координаты концов второго отрезка.
Вывод в файл OUTPUT. TXT. Выводится слово "Yes", если общая точка есть, или слово "No" - в противном случае.
Ограничения: координаты целые и по модулю не превосходят 10 000, время 1 с.
Примеры
Ввод 1 Ввод 2
0 0 0 0
1 0 1 0
1 0 2 0
1 1 3 0
Вывод 1 Вывод 2
Yes No
11.9. Выпуклая оболочка (7)
Найти выпуклую оболочку множества точек методом Грэхема.
Ввод из файла INPUT. TXT. В первой строке находится число N (1 ≤ N ≤ 105) , задающее количество точек. Следующие N строк содержат пары целых чисел - координаты точек (Xi, Yi).
Вывод в файл OUTPUT. TXT. В первой строке выводится M – количество вершин минимальной оболочки. Следующие N строк содержат пары целых чисел - координаты вершин (Xi, Yi) в порядке обхода против часовой стрелки, начиная от самой левой из самых нижних вершин.
Ограничения: координаты целые и по модулю не превосходят 10000, время 1 с.
Примеры
Ввод
6
0 0
2 2
2 0
0 2
1 1
1 0
Вывод
4
0 0
2 0
2 2
0 2
11.10. Газон (6)
Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы. В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены. Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r. Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье? Требуется написать программу, которая позволит дать ответ на вопрос Ивана.
Ввод из файла INPUT. TXT. В первой строке содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000). Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)
Вывод в файл OUTPUT. TXT. Вывести одно число - количество пучков травы, которые были и пострижены, и политы.
Пример
Ввод
0 0 5 4
4 0 3
Вывод
14
Иллюстрация к примеру
11.11. За решеткой (6)
Два бегемота, Вася и Эдик, живут в зоопарке. Каждый живет в отдельной прямоугольной клетке, три стены которой каменные, а четвертая образована решеткой. Через решетки бегемоты видят друг друга. Однажды ночью обоих мучила бессонница, и Вася предложил сыграть в морской бой, чтобы скоротать время. Чтобы сообщать о своем ходе как можно тише (ночь все-таки, все остальные звери спят), Эдик предложил найти такие положения около решеток, расстояние между которыми минимально.
Ввод из файла INPUT. TXT. В единственной строке задаются через пробел восемь чисел: сначала описание первой решетки, затем второй. Каждая решетка задается координатами концов (x1, y1, x2, y2). Все числа целые, по модулю не больше 10000.
Вывод в файл OUTPUT. TXT. В единственной строке вывести минимальное расстояние, которое может быть между Васей и Эдиком, если каждый будет стоять около своей решетки. Расстояние должно быть выведено с тремя знаками после запятой.
Пример
Ввод
0 1 0 5 1 -1 1 0
Вывод
1.414
11.12. А у нас в квартире газ (6)
В некотором районе проводится всеобщая газификация. Для этого прежде всего нужно построить газораспределительную станцию. Она может располагаться только на участке магистрального газопровода, соединяющего по прямой пункты A и B. На карте района известны координаты этих пунктов (u1, v1) и (u2, v2) соответственно. От станции протягиваются отдельные прямолинейные трубы к N (N ≤ 100) населенным пунктам c координатами (xi, yi) (-100 ≤ xi, yi ≤ 100). Известно, что затраты на проведение газовой трубы равны квадрату длины трубы. Требуется указать такие координаты газораспределительной станции, чтобы общие затраты на трубы были минимальны.
Ввод из файла INPUT. TXT. В первой строке задается значения N. Во второй строке указываются через пробел u1, v1, u2, v2. В следующих N строках задаются через пробел координаты xi, yi населенных пунктов.
Вывод в файл OUTPUT. TXT. Вывести с десятью знаками после запятой: в первой строке координаты станции, во второй строке минимальную стоимость труб.
Пример
Ввод
2
0 0 4 4
1 1
3 3
Вывод
2.0000000000 2.0000000000
4.0000000000
11.13. Длина линии (6)
Имеется круг радиуса R с центром в начале координат. Заданы две точки (X1,Y1) и (X2,Y2). Требуется найти минимальную длину линии, соединяющей эти точки, но не пересекающей внутренность круга.
Ввод из файла INPUT. TXT. В первой строке находится целое число N – количество блоков входных данных. Далее следуют N строк, каждая из которых содержит пять вещественных чисел через пробел – X1, Y1, X2, Y2 и R.
Вывод в файл OUTPUT. TXT. Для каждого блока входных данных выводится одно вещественное число с двумя знаками после запятой - минимальная длина линии.
Пример
Ввод
2
1, 1, -1, -1, 1
1, 1, -1, 1, 1
Вывод
3.571
2.000
11.14. Распил бревен (9)
Лесопильный комбинат выполняет заказ на распил брусьев для строительства детского городка. Все готовые брусья должны иметь форму треугольных призм, основаниями которых являются равнобедренные треугольники. Для изготовления брусьев закуплены заготовки в виде половинок продольно распиленных бревен. Заготовки не являются идеальными половинками цилиндров, поэтому при изготовлении бруса необходимо учитывать форму заготовок. Комбинат заинтересован в изготовлении бруса с наибольшей возможной площадью поперечного сечения.
Для каждой заготовки измеряется несколько сечений. Каждое из них задано в виде ломаной, представленной координатами ее вершин (x0, y0), (x1, y1), …, (xN, yN) в порядке их следования. Координаты вершин ломаной удовлетворяют следующим условиям:
· x0 < x1 < x2 < … < xN;
· xi = 0 для некоторого 0 < i < N;
· y0 = yN = 0
· для всех i от 1 до (N -1) выполнено условие yi > 0.
С учетом описанных требований необходимо найти максимально возможную площадь равнобедренного треугольника, удовлетворяющего следующим условиям:
· основание треугольника лежит на оси абсцисс;
· основание симметрично относительно начала координат;
· треугольник полностью лежит внутри каждого из измеренных сечений заготовки.
Требуется написать программу, которая по заданным сечениям заготовки вычислит максимально возможную площадь искомого равнобедренного треугольника.
Ввод. Первая строка входного файла содержит целое число K – количество измеренных сечений. Далее следуют описания каждого из K сечений. В первой строке описания сечения содержится число NK – количество звеньев ломаной. За ней следуют (NK +1) строк, каждая из которых содержит пару целых чисел xi и yi – координаты вершин ломаной сечения в порядке их следования.
Вывод. Выходной файл должен содержать одно вещественное число – наибольшую возможную площадь треугольника. Эта площадь должна иметь абсолютную или относительную погрешность не более 10-6, что означает следующее. Пусть выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным, если значение выражения |x - y| / max{1, |y|} не превышает 10-6.
Примеры
Ввод
2
5
-6 0
-3 5
-2 4
0 6
2 3
5 0
5
-6 0
-2 3
-1 6
0 6
1 6
7 0
Вывод
25.0
