Поиск пятиугольника с максимальным количеством точек

Описание

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

Формулировка задачи

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

Алгоритм

Программа использует полный перебор всех возможных комбинаций из 5 точек для построения пятиугольников. Для каждого пятиугольника проверяется:

• Уникальность вершин (отсутствие совпадающих точек)
• Отсутствие самопересечений сторон
• Отсутствие коллинеарных точек на сторонах
• Количество точек, лежащих внутри пятиугольника (используется алгоритм ray casting)

Использование

1. Подготовьте файл input.txt с координатами точек в формате:

   x1 y1
   x2 y2
   ...
   xn yn
   

2. Запустите программу:

   g++ курсач.cpp -o pentagon
   ./pentagon

3. Введите количество точек N при запуске программы

4. Результаты будут сохранены в файлах:

   • rez.txt - пятиугольник с максимальным количеством точек внутри
   • protokol.txt - протокол работы программы со всеми найденными пятиугольниками

Входные данные

Файл input.txt содержит координаты точек, по одной паре координат (x, y) на строку.

Выходные данные

• rez.txt - координаты вершин пятиугольника с максимальным количеством точек внутри и координаты этих точек
• protokol.txt - полный протокол работы программы со всеми найденными пятиугольниками

Автор

Бобков Владислав Дмитриевич,

Дата

Начало: 19.11.2021
Конец: 10.12.2021