Примеры презентаций для 2022

1. КУРСОВАЯ РАБОТА по дисциплине: «Объектно-ориентированное программирование» Задача №1111 «Квадраты»

2.

Постановка задачи

3.

Time limit: 0.5 секунд
Описание: Даны n (1 ≤ n ≤ 50) квадратов и точка P.
Расстояние между P и квадратом равно минимальной
длине отрезка, соединяющего P с точкой на периметре или
во внутренней области квадрата. В случае, когда P лежит
внутри квадрата, расстояние равно нулю. Некоторые
квадраты могут быть точками, то есть все вершины
квадрата могут совпадать. Напишите программу, которая
отсортирует квадраты в порядке возрастания расстояния до
точки P.

4.

Исходные данные: Первая строка содержит целое число n.
Следующие n строк содержат по четыре целых числа из
диапазона (−9999, 9999). Первые два числа задают x и y
координаты одной из вершин квадрата, следующие два
числа задают положение противоположной вершины.
Последняя строка содержит x и y координаты точки P.
Результат: вывести строку, содержащую номера квадратов,
отсортированных по расстоянию до точки P. Номера
квадратов заданы порядком, в котором квадраты даны во
вводе. Если у двух квадратов одинаковое расстояние до
точки P, то первым в списке должен идти меньший номер.
При сравнении расстояний точности 10−14 достаточно.

5.

Таблица соответствий входных и выходных данных

6.

Что делает программа?
• Получает со стандартного потока ввода информацию о
количестве квадратов, о координатах двух противоположных вершин каждого квадрата, а также координаты
точки P.
• Вычисляет расстояние от каждого квадрата до точки P,
производит сравнение вычисленных расстояний и
дальнейшую их сортировку.
• Выводит на стандартный поток вывода строку, содержащую номера квадратов, отсортированных по расстоянию до точки P.

7.

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

8.

Рис. 1 – Вектор и его проекции

9.

Координаты вектора:
Модуль вектора:
a ax a y
2
2
x2 x1 y2 y1
2
2

10.

Рис. 2 – Угол между векторами a и b

11.

Угол между векторами определяется по формуле:
cos
a b
a b
a x bx a y by
a x a y bx by
2
2
2
2

12.

Алгоритм решения
1) Для начала найдём угол между вектором, проходящим
через две вершины квадрата, и вектором (1, 1). Для этого
воспользуемся соответствующей формулой.
cos
a b
a b
a x bx a y by
a x a y bx by
2
2
2
2

13.

14.

Вычислим отдельно модуль вектора a:
cos
a b
a b
a x bx a y by
a x a y bx by
2
2
2
2

15.

Вычислим отдельно модуль вектора a:
cos
a b
a b
a x bx a y by
a x a y bx by
2
2
2
2

16.

2) Знаменатель обратится в нуль тогда и только тогда, когда
длина вектора, проходящего через две противоположные
вершины квадрата, станет равна нулю. Поэтому
необходимо рассмотреть два случая:
• Знаменатель не равен нулю
• Знаменатель равен нулю

17.

Если знаменатель не равен нулю, то:
1. Вычисляем угол между вектором диагонали и единичным вектором

18.

2. А также угол между вектором диагонали и горизонталью

19.

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

20.

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

21.

Определение положения вектора диагонали относительно
единичного

22.

4) После определения угла между векторами и его знака,
мы можем «довернуть» известные по условию точки
квадрата на найденный угол.
Поворот осуществляется с использованием
поворота в двумерном пространстве:
x1 cos
y1 sin
sin x
cos y
матрицы

23.

Рис. 3 – Поворот квадрата и точки
P

24.

а)
б)
Рис. 4 – Поворот квадратов вокруг начала
координат

25.

5) После поворота квадрата его стороны стали параллельны
осям координат. Теперь необходимо найти "границы"
квадрата по оси OX и по оси OY. Эти границы делят
плоскость на 9 различных зон (см. рис. 3).

26.

Рис. 5 – Различные случаи положения точки P на
плоскости

27.

6) Далее начинается разбор вариантов положения точки P
относительно квадрата. Эта точка может располагаться в
одной из этих девяти зон (см. рис. 3). После этого находим
расстояние от точки P до ближайшей точки на периметре
квадрата.

28.

Рис. 5 – Различные случаи положения точки P на
плоскости

29.

7) Наконец сортируем найденные расстояния от точки P до
каждого квадрата и выводим на экран строку, содержащую
номера квадратов, отсортированных по расстоянию от
точки P.

30. Конец

КОНЕЦ
Выполнил студент группы КС 5210
Каримов Андрей