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

А здесь уже никак... Придется перебирать.

Почему N^3? Перебрать все пары это N*(N-1)/2. Для каждой пары надо брать соседний отрезок снизу у минимального отрезка из этой пары, если он образует треугольник. Если не образует — выкидываем эту пару вообще, образует — запоминаем для поиска максимума.

franchukroman, я смотрю, отмечено как «решено». А где решение-то?

Так Alv привел. Теоретически правильное. Тесты прошло. Что еще надо?

А еще надо, чтобы это было не дорешивание :)

>Так Alv привел. Теоретически правильное. Тесты прошло. Что еще надо?

Ну как чего? Доказательство конечно же :)

Я в питоне вообще 0. Расшифровать эти каракули не могу.

И сколько времени тест проходит?

чую, что завершится очень быстро, но пока не вижу как просто доказать.
Фишка в том, что сходится эта хрень будет очень быстро.
Главное - не проверять лишнего. Т.е. правило треугольника при сортированном массиве позволяет покидать loops очень рано и можно показать, что далее сравнения делать не надо из-за сортированности массива (break позволяет быстро покинуть, так как последующие тем более не будут удовлетворять правилу треугольника):

/* sort first (NlogN) */

int i=0;
int j=1;
int k=1;
int last_big_sum=0;
int last_big_i, last_big_j, last_big_k; /* если необходимо */

while(i<10000-2){
   for(j=1;j<10000-1-i;j++){
      for(k=1;k<10000-j;k++){
if(l(i)<l(j)-l(k)) continue; /* do not calculate */
         s=...    /* calculate S by Heron */
         if(s>last_big_sum){
            /* last_big_sum=s; last_big_i=i, last_big_j=j, last_big_k=k */
         }
         if(if(l(i)>l(j)+l(k)) break; /* next will be even smaller */
      }   
   }
}

не тестировал, может и намудрил с каким индексом.

сорри за индентацию. Там 3 лупа, краткая иллюстрация:

0 ... i ... j ... k ... 10000

j всегда будет после i, а k - после j. Нет необходимости проверять предыдущие, так как из-за сортированности массива уж точно не удовлетворится правило треугольника. У правила треугольника вообще-то 3 проверки, но одна не имеет смысла (массив сортирован), а две других мы делаем. А 3я проверка и сортированность позволяет покидать цикл рано (если сумма 2х сторон меньше чем l(i), то следующий к будет ещё меньше).

зачем 3 цикла-то? Два достаточно. Ближайший снизу ко второму элемент даст масимальныую площадь среди всех остальных третьих.

не очевидно

S = 1/2 * |a| * |b| * cos(угол ab);
Берём 2 стороны.
Чем больше угол, тем больше площадь при углах меньше 90°. Угол тем больше, чем больше третья сторона. Если третий меньше 2 других, то угол меньше 90°. Значит третьей стороной должен быть соседний снизу отрезок, прилегающий к меньшему из пары.

сейчас влом тестировать (хорошо бы запустить оба решения)

ok, makes sense

не косинус, а синус конечно же.

кстати, в моём коде опечатки (торопился, не туда скопировал) исправлено

int i=0, j, k, last_big_sum=0;
int last_big_i, last_big_j, last_big_k; /* if necessary */

while(i<10000-2){
	for(j=1;j<10000-1-i;j++){
		for(k=1;k<10000-j;k++){
			if(l(i)<l(j)-l(k)) continue; /* do not calculate */
			if(l(i)>l(j)+l(k)) break; /* next will be even smaller */
			s=... /* calculate S by Heron */
			if(s>last_big_sum){
				last_big_sum=s; last_big_i=i, last_big_j=j, last_big_k=k
			}
		}
	}
}

Ну как чего? Доказательство конечно же :)

На предыдущей странице. Хотя оно намного понятнее, если при этом смотреть на график y = формула Герона в которой две стороны зафиксированы, а третья равна x.

Да при чем тут питон? Я в нем тоже почти нуль. Alv несколькими постами перед кодом сформулировал свою идею. Я ее реализовал на своих любимых плюсах.

За 0.244 самый толстый тест. Это без оптимизаций (точнее, единственная оптимизация - целочисленная арифметика, а можно было бы запилить еще и сортировку подсчетом и еще кучу всего).

PS. Почти на 100% идентичная задача на сайте, доступном для анонимусов: http://acmp.ru/index.asp?main=task&id_task=594 - подобные ограничения + парсер ввода, но меньше ограничения на длину максимального пути.

for (i = MaxN; i >= 2; --i)
    for(j = i - 1; j >=1; --j)
    {
        if (s[i] > s[j] + s[j-1]) // получается треугольник
        {
           s = heron(s[i], s[j], s[j-1]);
           if (s > MaxS) 
           {
               MaxS = s; 
               MemoryMaxS(i, j, j-1);
           }
        }
    }

s = heron(s, s[j], s[j-1]);

Компилятор очень обрадуется.

PS. Квадрат - много.

Алгоритм: перебирать соседние тройки сторон.
Можно начать перебирать с бОльших; как только найдем те, что образуют треугольник - можно останавливаться.

Доказательство:
Пусть дан треугольник.
Тогда увеличение не самой большой стороны (если она остается такой в процессе увеличения)
1) Не ломает треугольник, т.е. не нарушает неравенство треугольника
2) Не уменьшает площадь.

(это очевидно и уже доказывалось в треде)

Следовательно,
а) Можно перебирать только соседние тройки
б) Можно выбирать максимальную тройку, удовлетворяющую неравенству треугольника.

--Математик, участник финала ACM ICPC.

Кстати, кажется, не все участники треда понимают, что такое олимпиадная задача.

Не, вру, самую большую нельзя.

То самое более-менее строгое доказательство алгоритма Alv-а. Спасибо.

>Можно начать перебирать с бОльших; как только найдем те, что образуют треугольник - можно останавливаться.

пусть имеем «вершину» отсортированного списка 25, 14, 13, 12...
треугольник 25-14-13 имеет меньшую площадь, чем 14-13-12
и таких «регрессий» может быть сколько угодно...

Да, я уже написал, что ошибся.

10 000 000 случайных чисел-отрезков, всё решение вместе с созданием данных, сортировкой, последующим поиском занимает секунду

#include <vector>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

const long Max = 10000000;
vector<double> l(Max);

void FillRandom(vector<double>* v)
{
	srand(time(NULL));
	double m = 1.0 / double(RAND_MAX);
	for(size_t i = 0; i < v->size(); ++i)
	{
		(*v)[i] = m * rand();
	}
}

double Heron(double a, double b, double c)
{
	double p = 0.5*(a+b+c);
	double s = sqrt(p*(p-a)*(p-b)*(p-c));
	return s;
}
double HeronSimple(double a)
{
	// площадь равностороннего треугольника с единичной длинной сторон равна sqrt(0.1875),
	// площадь других равносторонних пропорциональна квадрату линейных размеров
	return sqrt(0.1875) * a * a;
}

int main(int, char *[])
{
	double MaxS = -1.0, max1 = 0, max2 = 0, max3 = 0;

	FillRandom(&l);

	sort(l.begin(), l.end());

	for(size_t i = l.size() - 1; i >= 2; --i)
	{
		if (HeronSimple(l[i]) <= MaxS) // бо́льшую площадь уже нельзя получить
		{
			break;
		}
		for(size_t j = i - 1; j >= 1; --j)
		{
			double l1 = l[i], l2 = l[j], l3 = l[j-1];
			if (l1 < (l2 + l3)) // треугольник существует
			{
				double s = Heron(l1, l2, l3);
				if (s > MaxS)
				{
					MaxS = s; max1 = l1; max2 = l2; max3 = l3;
				}
			}
		}
	}

	cout << setprecision(10) << "S=" << MaxS  << ": a =" << max1 << " b=" << max2 << " c=" << max3 << endl;

	return 0;
}

Доказать не возьмусь, но интуитивно кажется верным.

Фигня, сразу очевидно. Экстремальный пример: 2,3,4,1000,2000,3000. Из самых длинных получается вырожденный треугольник площадью 0. Из самых коротких — невырожденный.

зачем второй цикл?

Ну значит надо идти вдоль всего списка. Хотя ТС там чего то сделал, говорит что работает.

Алгоритм: перебирать соседние тройки сторон.

Можно начать перебирать с бОльших; как только найдем те, что образуют треугольник - можно останавливаться.

Опять-таки: 2,3,4,1000,2000,3000. Самая большая тройка даёт треугольник площадью 0 (прописью: ноль). Я надеюсь, вы поверите, что аналогичный пример с невырожденными треугольниками тоже найдётся?

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

Так что, да: насчёт трёх последовательных сторон — идея правильная, но придётся перебрать все такие тройки. O(N) — фигня, особенно учитывая, что нам и так нужна сортировка (O(N logN)).

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

А как вы без перебора найдете максимальную площадь?

ещё раз:
1. список отсортирован
2. ищем первые 3 идущих подряд стороны, начиная с наибольших, дающих треугольник - считаем площадь (первая максимальная) и минимальный периметр для него
3. начиная со второй стороны из пред. пункта опять берём 3 стороны подряд, если сумма периметра меньше найденного минимального - стоп, иначе - получается треугольник или нет. если да - считаем и сравниваем площади, если нет - сдвигаемся дальше и т.д.

Действительно ли среди треугольников со стороной Х площадь больше у тех, у которых больше периметр? Если это так, то второй цикл не нужен, если не так, то нужен.

Для треугольников со сторонами X, y, z, где X>=y>=z (для всех, причём y2=z1 и т.д., следует из отсортированности списка), площадь действительно будет больше у того, у кого больше периметр

Тоже никаких математических доказательств :)

Не факт, что меньший периметр даст меньшую площадь.

для найденной площади можно посчитать _минимальный_ периметр. И любой меньший его периметр уж никак не даст большую площадь.

рассматривать надо не случайный набор а наихудший

Периметр ИМНО тут не при делах - все равно в мин периметр не попадешь

Но больший периметр может дать меньшую площадь, так что как критерий оно не особо...

Зависимость площади от периметра - сложная функция, производная ее вполне может иметь несколько нулей (считать лень). Так что, не все так однозначно.

какая нахрен сложная функция... максимальная площадь на данный периметр - у равностороннего треугольника.

на отсортированном массиве - очень даже ничего. Если массив действительно случайных цифр - не более нескольких итераций

На несортированном массиве эта задача вообще номального решения не имеет.

Ну, если это доказано...

Наихудший это такой?
l(0) = 3
l(1) = 4
l(2) = 5
l(n) = l(n-1) + l(n-2) + 1

Для 100 000 таких элементов та программа работала 8 секунд.
Вот если бы ещё доказательство иметь того, что меньший периметр означает меньшую площадь для треугольника со сторонами Xconst >= a >= b

>Вот если бы ещё доказательство иметь того, что меньший периметр означает меньшую площадь для треугольника со сторонами Xconst >= a >= b

В пределе, когда Xconst = a = b - это и есть максимальная площадь, ибо треугольник равносторонний.

Ну а с доказательством - что-ж, дерзайте... ;)

Да.

8 сек - это очень долго, там N операций не считая сортировки.

>Вот если бы ещё доказательство иметь того, что меньший периметр означает меньшую площадь для треугольника со сторонами Xconst >= a >= b

Ну что, ни кто не «разродился»? =)

Пытался я вчера. Производные там довольно жуткие. В лом.