for i = 2 to n - 2
for j = i + 1 to n - 1
for k = j + 1 to n
...
next k
next j
next i
Задача, Разработать процедуру, помогите
Тема: Разработать процедуру.
Задача: Из заданного на плоскости множества точек выбрать три такие, которые составляют треугольник наименьшей площади.
Цитата:
Originally posted by NEON_UA
Помогите плз решить задачу, очень сложно...
Тема: Разработать процедуру.
Задача: Из заданного на плоскости множества точек выбрать три такие, которые составляют треугольник наименьшей площади.
Помогите плз решить задачу, очень сложно...
Тема: Разработать процедуру.
Задача: Из заданного на плоскости множества точек выбрать три такие, которые составляют треугольник наименьшей площади.
Плз помогите, даже идей нету. :(
Цитата:
Originally posted by NEON_UA
Плз помогите, даже идей нету. :(
Плз помогите, даже идей нету. :(
Код я тебе писать не буду, не жди. А вот идею расскажу. Площадь треугольника вычисляй по формуле Герона. После небольшой оптимизации она выглядит так: abs((X2 - X1)*(Y3 - Y1) - (X3 - X1)*(Y2 - Y1))/2. Abs - это модуль числа. Для удобства я бы на твоём месте объединил координаты точек в структуру (типа
private type Point
x as single
y as single
end type
), а вычисление площади вынес бы в отдельную функцию (напр. Square). В основной функции объявляешь переменную (напр. MinSquare as Single), где хранить будешь площадь минимальную, и присваеваешь ей значение площади от первых трёх точек. После этого, поскольку разницы в порядке перебора точек нет, пишешь набор вложенных циклов
Код:
внутри последнего из которых (вместо многоточия) вычисляешь площадь треугольника от точек pi, pj, pk. n у тебя - общее количество точек. Так вот полученную площадь ты сравниваешь с минимальной (на первм шаге она у тебя равна площади от первых трёх точек, помнишь? Именно поэтому индекс в первом for начинается с 2). И если полученная меньше минимальной, присваиваем значению минимальной площади значение только что полученной. А ещё и порядковые номера точек сохрани (т. е. i, j и k, до цикла значения переменных для хранения индексов у тебя должны быть равны 1, 2 и 3 соответственно). В итоге, после выхода из циклов, в переменной MinSquare у тебя будет минимальное значение площади, а номера точек, которые её дают, ты знаешь (потому что сохранил их). Всё. Задача на этом решена, а с тебя, как минимум, ОГРОМНОЕ СПАСИБО за то, что я не обломался поискать и модернизировать формулу, а ещё и столько строк печатного текста накрапать. Желаю удачи!
Хотя погоди, в цикле for i индексацию начинай с 1, я подзатупил немножко...
Спасибо большое. :)