Принадлежность точки отрезку

ЛАБОРАТОРНАЯ №5

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

A. Касательная к окружности

Даны координаты центра (x_c,y_c) и радиус R окружности, координаты точки (x,y). Найти точки пересечения касательных с окружностью.

Формат входных данных

Пять вещественных чисел x_c y_c R x y — коорди-наты центра и радиус окружности, координаты точки.

Формат выходных данных

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

Пример

input.txt	output.txt	Примечание
1 1 1 2 2	2 1.00 2.00 2.00 1.00
10 10 5 10 7	0	Точка лежит внутри окружности

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

Вычислите площадь произвольного n – угольника, заданного координатами своих вершин (x_i,y_i), i =1,2,…, n, в порядке обхода по часовой стрелке.

Пример

INPUT.TXT	OUTPUT.TXT
3 0 0 0 1 1 0	0.5

 

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

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

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

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

Вывод. Вывести одно число - длину периметра с одним знаком после запятой.

Примеры

input.txt	output.txt
5 1 0 0 1 -1 0 0 -1 0 0	5.7

 

 

Индивидуальные задания

Принадлежность точки отрезку

Даны координаты точки (x,y) и координаты концов отрезка (x₁,y₁) и (x₂,y₂). Принадлежит ли точка заданному отрезку.

Формат входных данных

Шесть вещественных чисел x y x ₁ y ₁ x₂ y₂ — координаты точки и координаты концов отрезка.

Формат выходных данных

Одна строка ‘YES’, если точка принадлежит отрезку, и ‘NO’ в противном случае.

Пример

input.txt	output.txt
3 3 12 5 4	YES

 

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

Даны координаты точки (x,y) и коэффициенты А, В и С нормального уравнения прямой. Принадлежит ли точка (x,y) заданной прямой Ax+By+C=0.

Формат входных данных

Пять вещественных чисел x y A B C — координаты точки и коэффициенты нормального уравнения прямой.

Формат выходных данных

Одна строка ‘YES’, если точка принадлежит прямой, и ‘NO’ в противном случае.

Пример

input.txt	output.txt
3 7 -2 1 -1	YES

 

Принадлежность точки лучу

Даны координаты точки (x,y) и координаты начала и конца вектора (x₁,y₁) и (x₂,y₂). Принадлежит ли точка (x,y) лучу определяемому заданным вектором.

Формат входных данных

Шесть чисел x y x ₁ y ₁ x₂ y₂ — координаты точки и координаты начала и конца вектора.

Формат выходных данных

Одна строка ‘YES’, если точка принадлежит лучу, определяемому вектором, и ‘NO’ в противном случае.

Пример

input.txt	output.txt
1 6 3 7 5 8	NO

 

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

Даны координаты двух точек (x₁,y₁) и (x₂,y₂) вне прямой с нормальным уравнением Ax+By+C=0.

Формат входных данных

Семь вещественных чисел x 1 y 1 x 2 y 2 A B C — координаты двух точек вне прямой и коэффициенты нормального уравнения.

Формат выходных данных

Одна строка "YES", если точки лежат по одну сторону прямой, и "NO" в противном случае.

Пример

input.txt	output.txt
0 0 2 4 2 -1 -1	YES

 

Расстояние от точки до луча

Даны координаты точки (x,y) и координаты начала и конца вектора (x₁,y₁) и (x₂,y₂).

Формат входных данных

Шесть чисел x y x ₁ y ₁ x₂ y₂ — координаты точки и координаты начала и конца вектора.

Формат выходных данных

Одно число — расстояние от точки до луча, определяемого вектором. Результат вывести с точностью до четырех знаков после точки.

Пример

input.txt	output.txt
2 1 1 1 0 2	1.0000

 

Расстояние от точки до отрезка

Даны координаты точки (x,y) и координаты концов отрезка (x₁,y₁) и (x₂,y₂). Найти расстояние от точки до заданного отрезка. Результат вывести с точностью до четырех знаков после точки.

Формат входных данных

Шесть чисел — координаты точки и координаты концов отрезка.

Формат выходных данных

Одно число — расстояние от точки до отрезка.

Пример

input.txt	output.txt
0 4 2 3 2 5	2.0000

 

Пересечение двух отрезков

Даны координаты начала и конца двух отрезков (x₁,y₁), (x₂,y₂) (x₃,y₄) и (x₅,y₆). Пересекаются ли заданные отрезки.

Формат входных данных

Восемь вещественных чисел x₁ y₁ x₂ y₂ x₃ y₄ x₅ y₆ — координаты начала и конца двух отрезков.

Формат выходных данных

Одна строка ‘YES’, если отрезки имеют общие точки, и ‘NO’ в противном случае.

Пример

input.txt	output.txt
5 1 2 6 1 1 7 8	YES

 

 

Симметричная точка

Дано уравнение прямой ax+by+c=0 и координаты точки (x,y). Найти координаты симметричной точки относительно заданной прямой.

Входные данные. В первой строке заданы два вещественных числа x и y - координаты точки заданной точки, во второй три числа a, b, c - коэффициенты заданной прямой.

Выходные данные. В первой строке с точностью до трех знаков

координаты симметричной точки.

Примеры

input.txt	output.txt
1 0 0 3 6	-3 6

Указание. Нормаль направлена в сторону возрастания градиента.

    

Окружность и прямая

Даны координаты центра (x_c,y_c) и радиус R, и коэффициенты А, В и С нормального уравнения прямой. Найти точки пересечения прямой с окружностью.

Формат входных данных

Шесть вещественных чисел x_c y_c R A B C — координаты центра и радиус окружности, и коэффициенты нормального уравнения прямой.

Формат выходных данных

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

Пример

INPUT.TXT	OUTPUT.TXT
1 1 1 1 -10	2 1.70711 1.70711 0.29289 0.29289

 

Квадрат

Даны координаты противоположных углов квадрата (x₁,y₁) и (x₂,y₂). Найти координаты двух других вершин.

Формат входных данных

Даны четыре вещественных числа x₁ y₁ x₂ y₂ — координаты противоположных углов квадрата.

Формат выходных данных

В первой строке вывести координаты одной из найденных вершин, во второй – координаты другой.

Пример

input.txt	output.txt
0 0 2 2	0.0 2.0 2.0 0.0

 

Формат входных данных

В первой строке x₁ y₁ x₂ y₂ — координаты концов первого отрезка, во второй строке x₃ y₃ x₄ y₄ — координаты концов второго отрезка.

Формат выходных данных

Одно число — расстояние от точки до отрезка.

Пример

input.txt	output.txt	Примечание
1 3 3 3 1 1 3 2	1.000
1 1 3 2 1 2 3 1	0.000	Между пересекающимся отрезками расстояние равно 0.

 

Формат входных данных

Шесть чисел x y x ₁ y ₁ x₂ y₂ — координаты точки и координаты начала и конца вектора.

Формат выходных данных

Одно число — длина перпендикуляра. Результат вывести с точностью до четырех знаков после точки. Если перпендикуляр не лежит на луче напечатать -1.

Пример

input.txt	output.txt
1 1 3 0 3 4	2.0000

 

Поиск квадрата

 Даны координаты n точек (x _i,y _i) с целыми значениями, i =1,2,…, n (4≤n, |x_i|,|y_i|≤100). Найти координаты вершин одного из квадратов, из заданного множества точек. Существование гарантируется.

Пример

INPUT.TXT	OUTPUT.TXT
6 0 0 -1 1 -1 0 1 0 0 1 1 1	0 0 -1 1 -1 0 0 1

 

Кольцо

Даны координаты n точек (x _i,y _i), i =1,2,…, n (n ≤100, x _i+y _i ≠0). Определить кольцо с центром в начале координат, которое содержит все точки. Напечатать радиусы внутренней и наружной окружностей найденного кольца. Результат с точностью до трех знаков.

Пример

input.txt	output.txt
3 1 1 1 2 2 2	1.414 2.828

 

Круг

Даны координаты n точек (x _i,y _i), i =1,2,…, n (n ≤100). Указать номера тех точек, которые принадлежат кругу с центром в точке (x,y) и радиусом R. Результат вывести в порядке следования вводимых данных. Если таких точек нет, напечатать “0”.

Пример

input.txt	output.txt
3 1 1 1 2 2 3 3 3 2	1

 

 

Прямоугольник

Даны координаты n точек (x _i,y _i), i =1,2,…, n (n ≥1). Указать номера тех точек, которые принадлежат прямоугольнику с координатами левого верхнего узла (a,b) и правого нижнего угла (c,d). Результат вывести в порядке следования вводимых данных. Если таких точек нет, напечатать “0”.

Пример

input.txt	output.txt
5 0 0 2.0 2.0 3 3 0.5 0.6 -0.7 -0.7 -1.0 1 1 -1	1 4 5

Треугольники

14.2. На плоскости n точек заданы своими координатами (x _i,y _i) , i =1,2,…, n и дана окружность радиуса R с центром в начале координат. Указать множество (номера) всех треугольников с вершинами в заданных точках и содержащихся внутри окружности. Номера вершин печатать в порядке возрастания значений, а также первый номер i-го треугольника должен быть меньше равно первого номера (i+1)-го треугольника. Если таких треугольников нет, напечатать “0”.

Пример

input.txt	output.txt
5 1 1 -2 -2 2 2 -1 1 0 0 2	1 4 5 2 5 7

 

Максимальный треугольник

На плоскости n точек заданы своими координатами (x _i,y _i) , i =1,2,…, n. Найти треугольник с максимальной площадью с вершинами в заданных точках. Напечатать площадь и номера вершин. Если их несколько, то напечатать любой из них.

Пример

input.txt	output.txt
5 0 0 0 2 1 0.5 0.5 1 2 0	2.00 1 2 5

 

Прямые

Прямая на плоскости может быть задана уравнением ax+by+c=0, где a и b одновременно не равные нулю. Пусть даны коэффициенты нескольких прямых a_i, b_i, c_i, i=1,...,n. Определите, имеются ли среди этих прямых совпадающие или параллельные. Ответ “YES” или “NO”.

Пример

input.txt	output.txt
3 1 3 5 2 6 15 1.2 4 67	YES

 

Касательная к окружности

Даны координаты центра (x_c,y_c) и радиус R окружности, координаты точки (x,y) вне окружности. Найти точку пересечения одной из касательных с окружностью.

Формат входных данных

Пять вещественных чисел x_c y_c R x y — координаты центра и радиус окружности, координаты точки.

Формат выходных данных

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

Пример

input.txt	output.txt	Примечание
1 1 1 2 2	1.00 2.00

 

Уравнение прямой

Даны координаты двух различных точек (x₁,y₁) и (x₂,y₂). Найти коэффициенты нормального уравнения Ax+By+C=0.

Формат входных данных

Четыре вещественных числа x₁ y₁ x₂ y₂ — координаты двух различных точек на прямой.

Формат выходных данных

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

Пример

input.txt	output.txt
1 2 3 1	-1.00 -2.00 5.00

 

Пересечение двух прямых

Даны коэффициенты А1,В1,С1 и A2,B2,C2 нормального уравнения двух различных непараллельных прямых (сначала для одной прямой, затем для другой).

Формат входных данных

Шесть вещественных чисел А1 В1 С1 A2 B2 C2 — коэффициенты нормального уравнения двух различных непараллельных прямых.

Формат выходных данных

Два числа — координаты точки их пересечения (с точностью 10^-4).

Пример

input.txt	output.txt
1 1 -1 1 -1 0	0.5000 0.5000

 

Формат входных данных

Пять чисел x y A B C — координаты точки и коэффициенты нормального уравнения прямой. С точностью до четырех знаков после точки.

Формат выходных данных

Одно число — расстояние от точки до прямой.

Пример

input.txt	output.txt
1 1 1 1 -1	0.70711

 

Точки в многоугольнике

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти число точек с целочисленными координатами, лежащих внутри многоугольника (не на границе). Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.

Ограничения: 3≤ N ≤10000, координаты вершин целые и по модулю не превосходят 1000000, время 1с.

Ввод из файла input.txt. В первой строке находится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится

заданный многоугольник.

Вывод в файл output.txt. Вывести одно число - искомое количество точек.

Примеры

input.txt	output.txt
4 -10 -10 -10 10 10 10 10 -10	361

 

Формат входных данных

Восемь вещественных чисел x₁ y₁ x₂ y₂ x₃ y₄ x₅ y₆ — координаты начала и конца двух отрезков.

Формат выходных данных

Напечатать координаты точки пересечения. Если не пересекаются напечатать -999.

Пример

input.txt	output.txt
0 0 1 1 0 1 1 0	0.5 0.5

 

2 6 . Принадлежность точки произвольному многоугольникуЗадан многоугольник и точка. Нужно определить, лежит ли точка внутри этого многоугольника. В этой задаче многоугольник невыпуклый.Входные данныеСначала вводится число N (3≤N≤100). Далее идут N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки.Выходные данныеВыведите сообщение YES, если точка лежит внутри многоугольника, или NO, если нет. Гарантируется, что точка не лежит на границе многоугольника.Пример

input.txt	output.txt
40 01 00.3 0.30 110 10	NO

 

27. Целые точки

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

Формат входных данных

В первой строке содержится N (3 ≤ N ≤ 1000) - число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 1000000.
Формат выходных данных

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

Примеры

input.txt	output.txt
4 -1 -1 -1 1 1 1 1 -1	1
3 0 0 0 2 2 0	0

 

Длина перпендикуляра

Даны координаты точки (x,y) и координаты концов отрезка (x₁,y₁) и (x₂,y₂). С точки (x,y) опущен перпендикуляр на заданный отрезок. Найти длину перпендикуляра.

Формат входных данных

Шесть чисел — координаты точки и координаты концов отрезка.

Формат выходных данных

Одно число — длину перпендикуляра. Если перпендикуляр не падает на отрезок вывести -1. Результат вывести с точностью до четырех знаков после точки.

Пример

input.txt	output.txt
0 4 2 3 2 5	2.0000
0 4 2 5 2 8	-1

 

Пересечение двух отрезков

Даны координаты начала и конца двух отрезков (x₁,y₁), (x₂,y₂) (x₃,y₄) и (x₅,y₆). Найти точку пересечения заданных отрезков.

Формат входных данных

Восемь вещественных чисел x₁ y₁ x₂ y₂ x₃ y₄ x₅ y₆ — координаты начала и конца двух отрезков.

Формат выходных данных

Одна строка – координаты точки пересечения, и -1 в противном случае.

Пример

input.txt	output.txt
1 2 5 4 1 5 5 1	3.0000 3.0000
1 2 5 4 0 0 4 0	-1

 

Вне круга

Даны координаты n точек (x _i,y _i), i =1,2,…, n (n ≤100). Указать номера тех точек, которые лежат вне круга с центром в точке (x,y) и радиусом R. Результат вывести в порядке следования вводимых данных. Если таких точек нет, напечатать “0”.

Пример

input.txt	output.txt
3 1 1 1 2 2 3 3 3 2	1

 

Максимальный квадрат

На плоскости задан прямоугольник размером W×H, и N отмеченных точек внутри него. Требуется найти квадрат максимального размера:

· со сторонами, параллельными сторонам прямоугольника;

· не содержащий отмеченных точек строго внутри себя (но, возможно, содержащий отмеченные точки на границе);

· лежащий внутри прямоугольника.

Формат входных данных

Первая строка входного файла содержит числа N — количество отмеченных точек, W — ширину прямоугольника и H — высоту прямоугольника (1 ≤ N ≤ 30000, 0 ≤ W, H ≤ 1000000). Следующие N строк содержат координаты отмеченных точек X_i, Y_i (целые числа, 0 ≤ X_i ≤ W, 0 ≤ Y_i ≤ H). Система координат введена так, что вершины прямоугольника имеют координаты (0, 0), (W, 0), (0, H), (W, H).

Формат выходных данных

Выведите в выходной файл одно число — длину стороны максимального искомого квадрата.

Примеры

Input.txt	Output.txt
7 10 73 24 27 07 34 52 41 7	4
1 10 105 5	5

 

 

ЛАБОРАТОРНАЯ №5

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

A. Касательная к окружности

Даны координаты центра (x_c,y_c) и радиус R окружности, координаты точки (x,y). Найти точки пересечения касательных с окружностью.

Формат входных данных

Пять вещественных чисел x_c y_c R x y — коорди-наты центра и радиус окружности, координаты точки.

Формат выходных данных

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

Пример

input.txt	output.txt	Примечание
1 1 1 2 2	2 1.00 2.00 2.00 1.00
10 10 5 10 7	0	Точка лежит внутри окружности

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

Вычислите площадь произвольного n – угольника, заданного координатами своих вершин (x_i,y_i), i =1,2,…, n, в порядке обхода по часовой стрелке.

Пример

INPUT.TXT	OUTPUT.TXT
3 0 0 0 1 1 0	0.5

 

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

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

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

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

Вывод. Вывести одно число - длину периметра с одним знаком после запятой.

Примеры

input.txt	output.txt
5 1 0 0 1 -1 0 0 -1 0 0	5.7

 

 

Индивидуальные задания

Принадлежность точки отрезку

Даны координаты точки (x,y) и координаты концов отрезка (x₁,y₁) и (x₂,y₂). Принадлежит ли точка заданному отрезку.

Формат входных данных

Шесть вещественных чисел x y x ₁ y ₁ x₂ y₂ — координаты точки и координаты концов отрезка.

Формат выходных данных

Одна строка ‘YES’, если точка принадлежит отрезку, и ‘NO’ в противном случае.

Пример

input.txt	output.txt
3 3 12 5 4	YES

 

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

Даны координаты точки (x,y) и коэффициенты А, В и С нормального уравнения прямой. Принадлежит ли точка (x,y) заданной прямой Ax+By+C=0.

Формат входных данных

Пять вещественных чисел x y A B C — координаты точки и коэффициенты нормального уравнения прямой.

Формат выходных данных

Одна строка ‘YES’, если точка принадлежит прямой, и ‘NO’ в противном случае.

Пример

input.txt	output.txt
3 7 -2 1 -1	YES

 

Принадлежность точки лучу

Даны координаты точки (x,y) и координаты начала и конца вектора (x₁,y₁) и (x₂,y₂). Принадлежит ли точка (x,y) лучу определяемому заданным вектором.

Формат входных данных

Шесть чисел x y x ₁ y ₁ x₂ y₂ — координаты точки и координаты начала и конца вектора.

Формат выходных данных

Одна строка ‘YES’, если точка принадлежит лучу, определяемому вектором, и ‘NO’ в противном случае.

Пример

input.txt	output.txt
1 6 3 7 5 8	NO

 

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

Даны координаты двух точек (x₁,y₁) и (x₂,y₂) вне прямой с нормальным уравнением Ax+By+C=0.

Формат входных данных

Семь вещественных чисел x 1 y 1 x 2 y 2 A B C — координаты двух точек вне прямой и коэффициенты нормального уравнения.

Формат выходных данных

Одна строка "YES", если точки лежат по одну сторону прямой, и "NO" в противном случае.

Пример

input.txt	output.txt
0 0 2 4 2 -1 -1	YES

 

Расстояние от точки до луча

Даны координаты точки (x,y) и координаты начала и конца вектора (x₁,y₁) и (x₂,y₂).

Формат входных данных

Шесть чисел x y x ₁ y ₁ x₂ y₂ — координаты точки и координаты начала и конца вектора.

Формат выходных данных

Одно число — расстояние от точки до луча, определяемого вектором. Результат вывести с точностью до четырех знаков после точки.

Пример

input.txt	output.txt
2 1 1 1 0 2	1.0000