Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2023-02-03 | 45 |
5.00
из
|
Заказать работу |
|
|
ЛАБОРАТОРНАЯ №5
Вычислительная геометрия
A. Касательная к окружности
Даны координаты центра (xc,yc) и радиус R окружности, координаты точки (x,y). Найти точки пересечения касательных с окружностью.
Формат входных данных
Пять вещественных чисел xc yc 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 – угольника, заданного координатами своих вершин (xi,yi), i =1,2,…, n, в порядке обхода по часовой стрелке.
Пример
INPUT.TXT | OUTPUT.TXT |
3 0 0 0 1 1 0 | 0.5 |
C. Выпуклая оболочка
На плоскости заданы N точек своими декартовыми координатами. Найти минимальный периметр многоугольника, содержащего все эти точки. Гарантируется, что искомый многоугольник имеет ненулевую площадь.
Ограничения: 3≤N≤1000, -10000≤xi, yi≤10000, все числа целые, все точки различны, время 2 с.
Ввод. В первой строке находится число N, далее - N строк с парами координат.
Вывод. Вывести одно число - длину периметра с одним знаком после запятой.
Примеры
input.txt | output.txt |
5 1 0 0 1 -1 0 0 -1 0 0 | 5.7 |
Индивидуальные задания
Принадлежность точки отрезку
Даны координаты точки (x,y) и координаты концов отрезка (x1,y1) и (x2,y2). Принадлежит ли точка заданному отрезку.
Формат входных данных
Шесть вещественных чисел x y x 1 y 1 x2 y2 — координаты точки и координаты концов отрезка.
|
Формат выходных данных
Одна строка ‘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) и координаты начала и конца вектора (x1,y1) и (x2,y2). Принадлежит ли точка (x,y) лучу определяемому заданным вектором.
Формат входных данных
Шесть чисел x y x 1 y 1 x2 y2 — координаты точки и координаты начала и конца вектора.
Формат выходных данных
Одна строка ‘YES’, если точка принадлежит лучу, определяемому вектором, и ‘NO’ в противном случае.
Пример
input.txt | output.txt |
1 6 3 7 5 8 | NO |
Положение точек вне прямой
Даны координаты двух точек (x1,y1) и (x2,y2) вне прямой с нормальным уравнением 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) и координаты начала и конца вектора (x1,y1) и (x2,y2).
Формат входных данных
Шесть чисел x y x 1 y 1 x2 y2 — координаты точки и координаты начала и конца вектора.
Формат выходных данных
Одно число — расстояние от точки до луча, определяемого вектором. Результат вывести с точностью до четырех знаков после точки.
Пример
input.txt | output.txt |
2 1 1 1 0 2 | 1.0000 |
|
Расстояние от точки до отрезка
Даны координаты точки (x,y) и координаты концов отрезка (x1,y1) и (x2,y2). Найти расстояние от точки до заданного отрезка. Результат вывести с точностью до четырех знаков после точки.
Формат входных данных
Шесть чисел — координаты точки и координаты концов отрезка.
Формат выходных данных
Одно число — расстояние от точки до отрезка.
Пример
input.txt | output.txt |
0 4 2 3 2 5 | 2.0000 |
Пересечение двух отрезков
Даны координаты начала и конца двух отрезков (x1,y1), (x2,y2) (x3,y4) и (x5,y6). Пересекаются ли заданные отрезки.
Формат входных данных
Восемь вещественных чисел x1 y1 x2 y2 x3 y4 x5 y6 — координаты начала и конца двух отрезков.
Формат выходных данных
Одна строка ‘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 |
Указание. Нормаль направлена в сторону возрастания градиента.
Окружность и прямая
Даны координаты центра (xc,yc) и радиус R, и коэффициенты А, В и С нормального уравнения прямой. Найти точки пересечения прямой с окружностью.
Формат входных данных
Шесть вещественных чисел xc yc R A B C — координаты центра и радиус окружности, и коэффициенты нормального уравнения прямой.
Формат выходных данных
В первой строке одно число К, равное количеству точек пересечения прямой с окружностью. Далее в К строках координаты самих точек.
Пример
INPUT.TXT | OUTPUT.TXT |
1 1 1 1 -10 | 2 1.70711 1.70711 0.29289 0.29289 |
Квадрат
Даны координаты противоположных углов квадрата (x1,y1) и (x2,y2). Найти координаты двух других вершин.
Формат входных данных
Даны четыре вещественных числа x1 y1 x2 y2 — координаты противоположных углов квадрата.
Формат выходных данных
В первой строке вывести координаты одной из найденных вершин, во второй – координаты другой.
Пример
|
input.txt | output.txt |
0 0 2 2 | 0.0 2.0 2.0 0.0 |
Формат входных данных
В первой строке x1 y1 x2 y2 — координаты концов первого отрезка, во второй строке x3 y3 x4 y4 — координаты концов второго отрезка.
Формат выходных данных
Одно число — расстояние от точки до отрезка.
Пример
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 1 y 1 x2 y2 — координаты точки и координаты начала и конца вектора.
Формат выходных данных
Одно число — длина перпендикуляра. Результат вывести с точностью до четырех знаков после точки. Если перпендикуляр не лежит на луче напечатать -1.
Пример
input.txt | output.txt |
1 1 3 0 3 4 | 2.0000 |
Поиск квадрата
Даны координаты n точек (x i,y i) с целыми значениями, i =1,2,…, n (4≤n, |xi|,|yi|≤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 одновременно не равные нулю. Пусть даны коэффициенты нескольких прямых ai, bi, ci, i=1,...,n. Определите, имеются ли среди этих прямых совпадающие или параллельные. Ответ “YES” или “NO”.
Пример
input.txt | output.txt |
3 1 3 5 2 6 15 1.2 4 67 | YES |
Касательная к окружности
Даны координаты центра (xc,yc) и радиус R окружности, координаты точки (x,y) вне окружности. Найти точку пересечения одной из касательных с окружностью.
Формат входных данных
Пять вещественных чисел xc yc R x y — координаты центра и радиус окружности, координаты точки.
Формат выходных данных
В первой строке одно число К, равное количеству точек пересечения касательных к окружности из заданной точки с самой окружностью. Далее в К строках координаты самих точек.
Пример
input.txt | output.txt | Примечание |
1 1 1 2 2 | 1.00 2.00 |
Уравнение прямой
Даны координаты двух различных точек (x1,y1) и (x2,y2). Найти коэффициенты нормального уравнения Ax+By+C=0.
Формат входных данных
Четыре вещественных числа x1 y1 x2 y2 — координаты двух различных точек на прямой.
Формат выходных данных
Три числа — коэффициенты А, В и С нормального уравнения этой прямой. Результат вывести с точностью до двух знаков после точки.
Пример
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 |
Формат входных данных
Восемь вещественных чисел x1 y1 x2 y2 x3 y4 x5 y6 — координаты начала и конца двух отрезков.
Формат выходных данных
Напечатать координаты точки пересечения. Если не пересекаются напечатать -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 строках идут координаты (Xi, Yi) вершин многоугольника в порядке обхода по часовой стрелке. Xi и Yi - целые числа, по модулю не превосходящие 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) и координаты концов отрезка (x1,y1) и (x2,y2). С точки (x,y) опущен перпендикуляр на заданный отрезок. Найти длину перпендикуляра.
Формат входных данных
Шесть чисел — координаты точки и координаты концов отрезка.
Формат выходных данных
Одно число — длину перпендикуляра. Если перпендикуляр не падает на отрезок вывести -1. Результат вывести с точностью до четырех знаков после точки.
Пример
input.txt | output.txt |
0 4 2 3 2 5 | 2.0000 |
0 4 2 5 2 8 | -1 |
Пересечение двух отрезков
Даны координаты начала и конца двух отрезков (x1,y1), (x2,y2) (x3,y4) и (x5,y6). Найти точку пересечения заданных отрезков.
Формат входных данных
Восемь вещественных чисел x1 y1 x2 y2 x3 y4 x5 y6 — координаты начала и конца двух отрезков.
Формат выходных данных
Одна строка – координаты точки пересечения, и -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 строк содержат координаты отмеченных точек Xi, Yi (целые числа, 0 ≤ Xi ≤ W, 0 ≤ Yi ≤ 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. Касательная к окружности
Даны координаты центра (xc,yc) и радиус R окружности, координаты точки (x,y). Найти точки пересечения касательных с окружностью.
Формат входных данных
Пять вещественных чисел xc yc 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 – угольника, заданного координатами своих вершин (xi,yi), i =1,2,…, n, в порядке обхода по часовой стрелке.
Пример
INPUT.TXT | OUTPUT.TXT |
3 0 0 0 1 1 0 | 0.5 |
C. Выпуклая оболочка
На плоскости заданы N точек своими декартовыми координатами. Найти минимальный периметр многоугольника, содержащего все эти точки. Гарантируется, что искомый многоугольник имеет ненулевую площадь.
Ограничения: 3≤N≤1000, -10000≤xi, yi≤10000, все числа целые, все точки различны, время 2 с.
Ввод. В первой строке находится число N, далее - N строк с парами координат.
Вывод. Вывести одно число - длину периметра с одним знаком после запятой.
Примеры
input.txt | output.txt |
5 1 0 0 1 -1 0 0 -1 0 0 | 5.7 |
Индивидуальные задания
Принадлежность точки отрезку
Даны координаты точки (x,y) и координаты концов отрезка (x1,y1) и (x2,y2). Принадлежит ли точка заданному отрезку.
Формат входных данных
Шесть вещественных чисел x y x 1 y 1 x2 y2 — координаты точки и координаты концов отрезка.
Формат выходных данных
Одна строка ‘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) и координаты начала и конца вектора (x1,y1) и (x2,y2). Принадлежит ли точка (x,y) лучу определяемому заданным вектором.
Формат входных данных
Шесть чисел x y x 1 y 1 x2 y2 — координаты точки и координаты начала и конца вектора.
Формат выходных данных
Одна строка ‘YES’, если точка принадлежит лучу, определяемому вектором, и ‘NO’ в противном случае.
Пример
input.txt | output.txt |
1 6 3 7 5 8 | NO |
Положение точек вне прямой
Даны координаты двух точек (x1,y1) и (x2,y2) вне прямой с нормальным уравнением 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) и координаты начала и конца вектора (x1,y1) и (x2,y2).
Формат входных данных
Шесть чисел x y x 1 y 1 x2 y2 — координаты точки и координаты начала и конца вектора.
Формат выходных данных
Одно число — расстояние от точки до луча, определяемого вектором. Результат вывести с точностью до четырех знаков после точки.
Пример
input.txt | output.txt |
2 1 1 1 0 2 | 1.0000 |
|
|
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!