Страницы

Уроки 57, 58 Взаимное расположение геометрических фигур

Напомним, точка на декартовой плоскости задается двумя числами: ее абсциссой и ординатой (х, у).

Расстояние между точками М1(х1,у1) и М2(х2,у2) на плоскости определяется по формуле:


В декартовых координатах каждая прямая определя­ется уравнением первой степени.

Общее уравнение прямой: Ах+Ву+С=0

Материал для чтения:

Если в общем уравнении прямой коэффициент при y не равен нулю (B<>0), то уравнение можно решить относительно у: y=-A/Bx-C/B. Обозначим k=-A/B и b=-C/B, получим уравнение вида y= kx+ b. Если же B=0, то уравнение примет вид x=-C/A.

Уравнение прямой с угловым коэффициентом

y = kx+b, где k — угловой коэффициент, b - величина отрезка, который отсекает прямая на оси 0у, считая от начала координат (рис. 1).


Уравнение прямой с угловым коэффициентом k, которая проходит через точку с координатами (х0; у0):
у—у0= k(x — x0)





Уравнение прямой, которая проходит через точки с координатами (х1,у1) и (х2,у2): 

 (y2-y1)/(x2-x1)=(y-y1)/(x-x1)  

Следовательно, с учётом 
Ах+Ву+С=0 можно получить:
A=y2-y1, B= x1-x2, C=-x1(y2-y1)+y1(x2-x1)   

                                         

Положение точек относительно прямой

1) Ax+By+C=0—определяет геометрическое место точек, лежащих на прямой.

Запишем программу для определения, лежит ли точка с координатами (х3; у3) на прямой, проходящей через точки (х1; у1) и (х2; у2). Переменная Р — переменная логического типа, которая имеет значение «истина», если точка лежит на прямой, и имеет значение «ложь» в про­тивном случае.

Фрагмент программы:

Var x1,y1,x2,y2,x3,y3: integer;
P:Boolean;
Begin
P:=false;
If (x3-x1)*(y2-y1)-(y3-y1)*(x2-x1)=0 then p:=true;


2) Ax+By+C>0— определяет геометрическое место точек, лежащих по одну сторону от прямой;

3) Ax+By+C<0— определяет геометрическое место точек, лежащих по другую сторону от прямой.

Вывод:

Точки (х3;у3) и (х4;у4) лежат по разные стороны от прямой, проходящей через точки (х1;у1),( х2;у2), если для этих точек значения выражений Ах3+Ву3+С и Ах4+Ву4+С имеют разные знаки;

Точки (х3;у3) и (х4;у4) лежат по одну сторону от прямой, проходящей через точки (х1;у1),( х2;у2), если для этих точек значения выражений Ах3+Ву3+С и Ах4+Ву4+С имеют одинаковые знаки.


Фрагмент программы:

L:=’ po odnu’;
Z1:=(x3-x1)*(y2-y1)-(y3-y1)*(x2-x1);
Z2:=(x4-x1)*(y2-y1)-(y4-y1)*(x2-x1);
If z1*z2<0 then l:=’ po raznie’;


Взаимное расположение двух отрезков



Отрезки на плоскости заданы координатами своих концевых точек, необходимо определить взаимное располо­жение двух отрезков. 

Предположим, что концевые точки одного из отрезков имеют координаты (х1,у1) и (х2,у2), а концевые точки другого — (х3;у3) и (х4;у4). Пусть общее уравнение первой прямой, проходя­щей через точки (х1,у1) и (х2,у2) имеет вид А1x + B1y+C1 = 0, а уравнение второй прямой, проходящей через точки (х3;у3) и (х4;у4), выглядит так: А2x + B2y+C2 = 0,



Определим расположение точек (х3;у3) и (х4;у4) относительно первой прямой. Если они расположены по одну сторону от прямой, то отрезки не могут пересекать­ся. Аналогично можно определить положение точек (х1,у1) и (х2,у2) относительно другой прямой.

Таким образом,
отрезки пересекаются, если значения пары выражений Z1=А1x3 + B1y3+C1 и Z2=А1x4 + B1y4+C1 разные знаки или Z1*Z2=0, а также пары Z3= А2x1+ B2y1+C2 и Z4= А2x2+ B2y2+C2 имеют разные знаки или Z3*Z4=0.

отрезки не пересекаются, если значения пар выражений Z1 и Z2 или Z3 и Z4 имеют одинаковые знаки.




Фрагмент программы для определения, пересекаются ли два отрезка с концами в точках (х1,у1) , (х2,у2) и (х3;у3), (х4;у4):

p:=true;
Z1:=(x3-x1)*(y2-y1)-(y3-y1)*(x2-x1);
Z2:=(x4-x1)*(y2-y1)-(y4-y1)*(x2-x1);
If z1*z2>0 then P:=false;
Z3:=(x1-x3)*(y4-y3)-(y1-y3)*(x4-x3);
Z4:=(x2-x3)*(y4-y3)-(y2-y3)*(x4-x3);
If z3*z4>0 then P:=false;




Примечание: Приведенный фрагмент алгоритма не учитывает крайней ситуации, когда два отрезка лежат на одной прямой: 
(x3-x1)(y2-y1)-(y3-y1)(x2-x1)=0 и (x4-x1)(y2-y1)-(y4-y1)(x2-x1)=0



На рис.4 отрезки, лежащие на одной прямой, не пересекаются, а на рис. 5 — пересекаются.

Для того чтобы определить взаимное расположение таких отрезков, поступим следующим образом. Обозначим k1 = min (x1; х2); k2 = max(x1; x2); k3 = min(x3; x4); k4 = max(x3; x4).

Здесь k1 является левой, a k2 — правой точкой проекции первого отрезка (отрезка, заданного координатами (x1;y1), (x2; у2)) на ось Ох. Аналогично k3 является левой, и k4 — правой точкой проекции второго отрезка (отрезка, заданного координатами (x3;y3), (x4; у4)) на ось Ох. Ана­логично ищем проекции на ось Оу.


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



Для определения взаимного расположения проекций на ось Ох воспользуемся следующим фактом (см. рис. 4 и 5): координата левой точки пересечения проекций Lx равна max(k1; k3), т. е. максимальной из координат левых точек проекций. Рассуждая аналогично для пра­вых точек проекций, получим, что координата правой точки Rx пересечения равна min (k2, k4). Для того чтобы отрезки пересекались, необходимо, чтобы левая коорди­ната пересечения проекций была не больше правой координаты пересечения отрезков (такой случай имеет место на рис. 4, когда Lx = x3, a Rx = x2). Поэтому услови­ем пересечения проекций является выполнение нера­венства Lx<=Rx.

Аналогично можно вычислить величины Ly и Ry, взяв соответствующие проекции на ось Оу.

Следует отметить, что длина пересечения проекций в этом случае равна величине Rx — Lx (если Rx — Lx = 0, то проекции имеют только общую точку).

Точка пересечения отрезков

Для определения места пересечения отрезков (если известно, что они пересекаются), достаточно определить точку пересечения прямых, на которых эти отрезки лежат.

Пусть A1x+B1y+C1=0— уравнение прямой, проходящей через концевые точки первого отрезка, а А2х+ В2у+С2=0 — уравнение прямой, проходящей через концевые точки второго отрезка.

Тогда для определения точки пересечения отрезков достаточно решить систему уравнений


Домножив первое уравнение на А2, а второе — на А1 получим

Вычитаем из первого уравнения второе и находим значение у:

Аналогично вычисляем значение х:

Это справедливо в случае, если А2*В1—А1*В2<>0. Но мы уже знаем, что отрезки пересекаются и не лежат на одной прямой, а это невозможно, если А2*В1—А1*В2 =0.

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

Входные данные
Входной файл INPUT.TXT содержит четыре числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из координат не превышает по абсолютной величине значения 109.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число – количество точек на заданном отрезке, имеющих целочисленные координаты.

Примеры
INPUT.TXT
OUTPUT.TXT
1
1 1 2 2
2
2
0 0 -2 -2
3
3
1 1 1 10
10


Задание 2. На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны 1, 2, 3, . . . . Также на плоскости задан отрезок, концы которого находятся в точках (x1, y1) и (x2, y2). Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

Входные данные
Входной файл INPUT.TXT содержит четыре целых числа: x1, y1, x2 и y2. Эти числа не превосходят 103 по абсолютной величине. Заданный отрезок имеет ненулевую длину.

Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – количество общих точек.

Примеры

INPUT.TXT
OUTPUT.TXT
1
1 1 2 1
1
2
1 2 2 1
0

Пояснение «Отрезок и окружности»
Для начала рассмотрим более простую задачу. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до центра координат возрастает. Для такого отрезка ответ очевиден – это количество целых чисел между расстояниями от центра координат до обоих концов отрезка.
Теперь необходимо свести данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом, исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к (0; 0) точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.
Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее.

Задание 3. Эта история происходила на одной плоской планете. С незапамятных времен на ней существовал город N, находящийся в точке xn,yn. Кроме этого, в разное время на этой же планете существовали страны, каждая из которых имела форму треугольника.
Теперь перед историками встала серьезная задача — по имеющимся у них данным о треугольных странах определить, в какие страны мог входить город N. Город мог входить в страну, если он находится строго внутри нее.


Входные данные
Первая строка входного файла содержит два числа: xn и yn — координаты города N. Вторая строка входного файла содержит количество k треугольных стран (1 ≤ k ≤ 1000). 
Последующие k строк каждая описывают одну треугольную страну. Описание треугольной страны состоит из шести целых чисел x1,y1,x2,y2,x3,y3, где (x1,y1), (x2,y2), (x3,y3) — координаты вершин этой страны.

Гарантируется, что все страны имеют ненулевую площадь. Все координаты не превосходят 10000 по абсолютной величине.

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


Примеры

INPUT.TXT
OUTPUT.TXT
1
0 1
2
-2 0 2 0 0 2
-3 0 3 0 0 3
2
1 2
2
0 2
2
-2 0 2 0 0 2
-3 0 3 0 0 3
1
2


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

Входные данные
Входной файл INPUT.TXT содержит в первой строке одно целое число N (3 ≤ N ≤ 1000) – количество отрезков. 
Во второй строке содержатся N целых чисел от 1 до 1000 – длины отрезков. Числа разделены пробелом.

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

Примеры

INPUT.TXT
OUTPUT.TXT
1
5
2 4 8 16 7
13.998
2
3
3 4 5
6.000
3
3
1 2 5
0