Среди заданного множества точек на плоскости выбрать 3 по условию - C (СИ)

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

Среди заданного множества точек на плоскости выбрать 3 такие, чтобы треугольник, вершинами которого эти точки являются, содержал бы наибольшее количество точек множества.

Решение задачи: «Среди заданного множества точек на плоскости выбрать 3 по условию»

Листинг программы

#include <stdio.h>
#include <conio.h>
 
#define NMAX 100
 
void main()
{
  double eps = 1e-3;
  int i,n, r1 = 0, r2 = 0, r3 = 0;
  int t,t1,t2,t3;
  float x[NMAX], y[NMAX];
  int maxcount = 0;
  printf("Vvedite kolvo tochek: ");
  scanf("%d", &n);
  for (i = 0; i < n; i++)
  {
    printf("x[%d] = ", i);
    scanf("%f", &x[i]);
    printf("y[%d] = ", i);
    scanf("%f", &y[i]);
  }
 
  for (t1 = 0; t1 < n; t1++)
     for (t2 = 0; t2 < n; t2++)
         for (t3 = 0; t3 < n; t3++)
        {
          int count = 0;
          for (t = 0; t < n; t++)
             {
               if ((t != t1) && (t != t2) && (t != t3) && (t1 != t2) && (t1 != t3) && (t2 != t3))
                 {
                   float v = (x[t]-x[t1])*(y[t2]-y[t1])-(y[t]-y[t1])*(x[t2]-x[t1]);
                   if ((((x[t]-x[t2])*(y[t3]-y[t2])-(y[t]-y[t2])*(x[t3]-x[t2]))*v>-eps) &&
                     (((x[t]-x[t3])*(y[t1]-y[t3])-(y[t]-y[t3])*(x[t1]-x[t3]))*v>-eps))
                     count++;
                }
       }
       if (count > maxcount) 
       {
          maxcount = count;
          r1 = t1;
          r2 = t2;
          r3 = t3;
       }
   }
    printf("Treugolnik s vershinami %d, %d, %d. kolvo tochek vnutri %d", r1, r2, r3, maxcount);
    getch();
}

Объяснение кода листинга программы

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

Подключение необходимых библиотек.
Объявление переменных:
- double eps = 1e-3; - задание точности вычислений.
- int i,n; - служебные переменные для циклов.
- int r1 = 0, r2 = 0, r3 = 0; - переменные для хранения координат вершин треугольника.
- int t,t1,t2,t3; - служебные переменные для циклов.
- float x[NMAX], y[NMAX]; - массивы для хранения координат точек.
- int maxcount = 0; - переменная для хранения количества вершин треугольника.
- printf(Vvedite kolvo tochek: ); - вывод запроса на ввод количества точек.
- scanf(%d, &n); - считывание количества точек.
- for (i = 0; i < n; i++) - цикл для ввода координат точек.
- printf(x[%d] = , i); - вывод запроса на ввод координаты по оси x.
- scanf(%f, &x[i]); - считывание координаты по оси x.
- printf(y[%d] = , i); - вывод запроса на ввод координаты по оси y.
- scanf(%f, &y[i]); - считывание координаты по оси y.
Поиск треугольника:
- for (t1 = 0; t1 < n; t1++) - внешний цикл по точкам.
- for (t2 = 0; t2 < n; t2++) - второй вложенный цикл по точкам.
- for (t3 = 0; t3 < n; t3++) - третий вложенный цикл по точкам.
- int count = 0; - переменная для подсчета вершин треугольника.
- float v = (x[t]-x[t1])*(y[t2]-y[t1])-(y[t]-y[t1])*(x[t2]-x[t1]); - вычисление коэффициента треугольника.
- `if ((((x[t]-x[t2])(y[t3]-y[t2])-(y[t]-y[t2])(x[t3]-x[t2]))*v>-eps) &&
- ((x[t]-x[t3])(y[t1]-y[t3])-(y[t]-y[t3])(x[t1]-x[t3]))*v>-eps))` - условие принадлежности точки к треугольнику.
- count++; - увеличение счетчика вершин.
- if (count > maxcount) - проверка, является ли текущий треугольник максимальным.
- maxcount = count; - обновление максимального количества вершин.
- r1 = t1; - сохранение координат вершин треугольника.
- r2 = t2;
- r3 = t3;
Вывод результата:
- printf(Treugolnik s vershinami %d, %d, %d. kolvo tochek vnutri %d, r1, r2, r3, maxcount); - вывод результата.
- getch(); - ожидание нажатия клавиши для завершения программы.