Поиск параллелограммов из множества точек Презентация проекта по информатике Автор: Панова Ирина 10-2
Этапы решения задачи Постановка задачи Входные и выходные данные Визуализация постановки задачи Математическая модель Визуализация структуры данных Визуализация метода решения Пример работы программы
Постановка задачи На плоскости заданы множество точек A и точка d вне его. Подсчитать количество(неупорядоченных)различных троек точек a,b,c из A таких,что четырехугольник abcd является параллелограммом. Содержание
Входные и выходные данные 1)Входные данные: Координаты точек из вводимого нами множества точек A. 2)Выходные данные: Количество найденных параллелограммов Содержание
Визуализация постановки задачи Имеем: множество точек и закрепленную точку d(красная): Требуется : Нахождение точек являющихся вершинами параллелограммов Вывести их кол-во на экран Рисовала множество точек и сами найденные параллелограммы. Содержание
Математическая модель Находим знаки косинусов внешних углов четырехугольника Проверяем равенство противоположных сторон Рис 1. Рис 2. Содержание
Визуализация структуры данных Имеется массив dots типа Coord хранящий координаты вводимого множества точек x1;y1x2;y2x3;y3x4;y4x5;y5x6;y6x7;y7x8;y8x9;y x3;y3x4;y4x6;y6x;y Координаты закрепленной точки Рабочий массив dots x3-x4;y3-y4x4-x6;y4-y6x6-x;y6-yx-x3;y-y3 Массив,хранящий координаты векторов, содержащих стороны 4-ка Содержание
Визуализация метода решения Имеются четыре выбранные точки и три варианта их обхода: В каждом из этих случаев проверяем знаки косинусов углов Если у 4-ка более 2х острых или тупых углов, то он невыпуклый Если при проверке 4-к оказался выпуклым, то проверяем его на равенство противоположных сторон, если они равны, то это параллелограмм. BC DA AB=CD AD=BC ABCD-параллелограмм Содержание
Пример работы программы Входные данные: Выходные данные: 2 параллелограмма y x Содержание
Возникшие затруднения Проверка четырехугольника на выпуклость
Спасибо за внимание! Презентацию подготовила Ученица 10-2 класса Панова Ирина Контактная информация: