Из множества точек найти треугольник максимальной площади и минимальной

Der_Sohn

Сама задача Из множества точек найти треугольник максимальной площади и минимальной Это срочно) Зарание спасибо!)
3 ответа

Der_Sohn


DEFINT I-K, N
DEF fns (x1, y1, x2, y2, x3, y3)
   fns = ABS((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2
END DEF
 
RANDOMIZE TIMER
CLS
INPUT "N = "; n
DIM x(1 TO n)
DIM y(1 TO n)
 
FOR i = 1 TO n
   x(i) = 20 * RND - 10
   y(i) = 20 * RND - 10
NEXT i
 
min = 1000
max = 0
FOR i = 1 TO n
   FOR j = 1 TO n
      IF j = i THEN 100
      FOR k = 1 TO n
      IF k = i OR k = j THEN 200
      s = fns(x(i), y(i), x(j), y(j), x(k), y(k))
      IF s > max THEN max = s
      IF s < min THEN min = s
200
      NEXT k
100
   NEXT j
NEXT i
PRINT " MAX = "; max
PRINT " MIN = "; min
END


Der_Sohn

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


Der_Sohn

Да! Вы правы!! Шанс получить нулевую площадь есть всегда. Но представьте, что числа вещественные - шанс очень мал. Что касается формулы, то она широко распространена в программировании. Вы правы она получена в аналитической геометрии. Модуль векторного произведения двух векторов равен площади параллелограмма, построенного на этих векторах (а половина и есть площадь треугольника). Спасибо вам за ваши замечания. Это не мелочи! Такая программа в реальной жизни может "дорого стоить" Спасибо!