Выбор трёх точек множества так, чтобы треугольник с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь

Учебный курс: Парадигмы программирования

Кафедра: ИС Факультет: ИТиП

Лабораторная работа №3

Выполнил: Смирнов Р.А.Группа: 2517

Преподаватель: Зинчик А. А.

Задание

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

struct point { int x, y;//структура, описывающая точку

};

class sets//класс, описывающий 2 множества

{

       private:

              point* set2;//указатель на первое множество

              point* set1;//указатель на второе множество

              int out_border2, out_border1;//предельные значения для координат точек 1 множества и 2 множества ВНИМАНИЕ! Значение border2 ДОЛЖНО БЫТЬ БОЛЬШЕ border1

              int point_quantity;//количество точек - одинаковое для обоих множеств

              point* cr_pt_arr();//метод, возвращающий массив из 8 "критических точек", имеющих максимальное по модулю значение отдельно по x и по y по 2 точки на каждую четверть. Если максимальное значение по x и по y имеет одна точка - то возвращаются 2 точки с одинаковыми значениями координат

              bool is_in_triangle (point pt_1, point pt_2, point pt_3, point pt);//метод, определяющий, лежит ли точка pt внутри треугольника с координатами вершин pt_1, pt_2, pt_3

       public:

              sets(int out_border2, int out_border1, int point_quantity);//метод(конструктор), задающий 2 множества точек

              void show_set1();//метод, выводящий на экран все точки 1 множества

              void show_set2();//-//- 2 множества

              void find_solution();//метод возвращающий 3 точки - координаты вершин минимального 3-ка, из точек множества set2, который покрывает все точки множества set1

              ~sets();

};