[геометрия] [задача] Дано отрезки, найти площадь самого большого треугольника

ох уж эта «вышка»...

Ладно, докажи, что при заданной вписанной окружности минимален периметр у равностороннего треугольника (или наоборот - что при заданном периметре вписанная окружность максимальна у равностороннего), если это и так не понятно

Из формулы S = pr следует, что при заданной площади периметр минимален при максимальной вписанной окружности, т.е. у равностороннего треугольника

Маааааать, люди, я понимаю, что слово «очевидно» у некоторых не в чести, но неужели ЭТО НЕ ОЧЕВИДНО?!!!!!

Очевидно, но доказать бы не помешало :)

как их факта «при заданной площади периметр минимален при максимальной вписанной окружности, т.е. у равностороннего треугольника» следует, что бо́льшему периметру всегда соответствует бо́льшая площадь у других видов треугольников?

1. насрать на остальные треугольники: мы для рассчитанной площади определяем минимальный периметр, и если очередная тройка сторон дает меньший периметр - аллес

2. Для треугольников типа Aconst >= b >= c и далее, где b[i] = c[i-1] и b[i] >= c[i] площадь будет только уменьшаться (вернее - не увеличиваться :)) из той-же формулы площади

>из той-же формулы площади

из формулы площади через высоту: S = 1/2 * Aconst * h

надеюсь не надо объяснять, что при уменьшении одной/обоих других сторон высота h будет ТОЛЬКО уменьшаться? =)

мы для рассчитанной площади определяем минимальный периметр, и если очередная тройка сторон дает меньший периметр - аллес

Для анонимуса подобная мысль, похоже, слишком сложна.

Берём треугольник с основанием 1 и высотой 0.1
Его площадь не меняется от перемещения основания вправо-влево S = 1/2 * Aconst * Hconst.

Поместим вершину так, чтобы перпендикуляр на основание был в точке 0.1, ведя отсчёт по основанию треугольника слева.
сторона слева sqrt(0.1² + 0.1²)=0.141421356 справа sqrt(0.1² + 0.9²)=0.905538514 сумма 1.04695987

Поместим вершину так, чтобы перпендикуляр на основание был в точке 0.5, т.е. посередине.
сторона слева sqrt(0.1² + 0.5²)=0.509901951 справа sqrt(0.1² + 0.5²)=0.509901951 сумма 1.019803902

Имеем при одинаковой площади разные периметры.

настолько сложна, что он выход из цикла так и запрограммировал

>при уменьшении одной/обоих других сторон высота h будет ТОЛЬКО уменьшаться? =)

С этого и надо было начинать, когда просили доказательства

>Имеем при одинаковой площади разные периметры.

Что ты этим хотел сказать?

Я о ненужности второго цикла.

Имеем _правильный_ треугольник с основанием Aconst и двумя другими сторонами, меньшими или равными основанию. Уменьшение любой из сторон или обоих (условие отсортированного массива) даст уменьшение площади. Баста.

>С этого и надо было начинать, когда просили доказательства

!!!!!!! Я думал это и так ясно...

> Уменьшение любой из сторон или обоих (условие отсортированного массива) даст уменьшение площади. Баста.

А уменьшение основания?;-)

уменьшение основания автоматически уменьшает стороны, так как основание рассматривавается первым при проходе отсортированного списка отрезков.

а думаю он меня «подкалывает» :)

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

если больше 90°.
S=0.5*|a|*|b|*sin(α)
Уменьшение основания при угле больше 90° даст увеличение площади, пока угол больше 90°.

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

// Наверно я тут единственный, кто не узрел в задаче хитрой геометрии. А без неё и задачи-то нет ><

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

Временную оценку этому дать сложно, может тут найдутся эксперты )

На самом деле всё это дерьмо, попадётся 10000,5000,5001 и кирдык :(

>Кстати, можно пройтись в один проход по неотсортированному массиву отрезков. Если видим отрезок, который нельзя засунуть в текущий треугольник, кидаем его в отдельный массив

в вырожденном случае в «отдельный массив» уйдёт весь твой неотсортированный массив за исключением первой пары сторон.

в обычном случае под конец цикла ты заманаешься на каждом шагу искать в «отдельном массиве», пусть даже с бинарным поиском, когда там будет почти весь твой неотсортированный массив

И в твоём «алгоритме» мы обязаны пройти цикл до конца. По отсортированному массиву мы сделаем менее 2n итераций, где n - разрядность длинны стороны

Есть мнение, что инта не хватит на такой вырожденный массив.

>На самом деле всё это дерьмо, попадётся 10000,5000,5001 и кирдык :(

это если, как ты сказал, просто искать большую сторону для одного единственного отрезка... Можно завести некоторое количество структур, равное максимально возможному количеству вырожденных случаев, и перебирая стороны, менять их в случае, если в некоторых треугольниках они дадут большую площадь, при этом «забывая» те треугольники, которые «в принципе» не смогут дать большую площадь.... Но оценку скорострельности такого алгоритма дать трудно (пока его не составишь :))

>Есть мнение, что инта не хватит на такой вырожденный массив.

почему? ты сам привёл пример. Обобщённо: x[0], x[1], все остальные x[i] < |x[0]-x[1]|

Хватит оправдываться - ты быдлокодер. Иди дальше пиши на сишечке и сиди под рутом

Да, я - быдлокодер. А ты - трус последний. Пиши из-под своего аккаунта, будь мужиком! =)

А может, у него нет своего аккаунта?

Есть. Наверняка =)

Я - anonymous, я пишу из под своего аккаунта. Окей, значит ты быдлокодер. Это круто. Ты умеешь признавать свои недостатки. Теперь такой вопрос: когда ты проследуешь в биореактор?