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

Что за турнир?

Отсортировать по длине и перебрать несколько самых, удовлетворяющих максимуму по формуле Герона?

1. Как минимум, ты должен проверять, что отрезки удовлетворяют неравенству треугольника |a-b| < c < a+b.

2. Существует формула Герона, которая связывает площадь с периметром — суммой длин сторон. Я бы как-то опирался на этот факт, т.к. с суммами работать легче

1) неравенство треугольника помнишь? Не каждые три отрезка дают треугольник.

опередил :)

2) чё тут считать то, задача сводится к поиску трёх чисел, удовлетворяющих теореме пифагора.

Эвристика от балды: завернуть все в Gift wrapper, в нем найти треугольник. За правильность не отвечаю

S=0.5*a*b*sin(gamma)
max(S) —> if gamma=90°
find max(c) —> a²+b²=c²

1. Как минимум, ты должен проверять, что отрезки удовлетворяют неравенству треугольника |a-b| < c < a+b.

Знаю. Если делать так, как я описал (в конце поста, медленный алгоритм), то при плохом треугольнике обязательно получится отрицательное значение под корнем (формула Герона). Дабы не ломать алгоритм, я корень считал прямо перед выводом результата (и вообще, свел всю арифметику к целым числам). Хотя можно было бы еще 2 бинарных деления, чтобы найти границы, где начинаются и кончаются годные треугольники, но сложность алгоритма от этого бы не изменилась.

2. Существует формула Герона, которая связывает площадь с периметром — суммой длин сторон. Я бы как-то опирался на этот факт, т.к. с суммами работать легче

Так я и исходил из формулы Герона.

2) чё тут считать то, задача сводится к поиску трёх чисел, удовлетворяющих теореме пифагора.

Какая теорема Пифагора? Треугольники не прямоугольные.

> 2) чё тут считать то, задача сводится к поиску трёх чисел, удовлетворяющих теореме пифагора.

1. Таких в выборке может не быть

2. Максимум при заданном _периметре_ достигается на равностороннем треугольнике

2. Максимум при заданном _периметре_ достигается на равностороннем треугольнике

1. Таких в выборке может не быть

2. Кто сказал, что вам задан периметр?

Как? Gift wrapper - искалка выпуклой оболочки, ее можно применить, имея вершины. А у нас есть только длины отрезков. Да и идея бредова.

> 1. Таких в выборке может не быть

А для алгоритма с периметром они и не нужны

2. Кто сказал, что вам задан периметр?

Если известны стороны, то периметр всегда есть.

Да, не годиться. Это я брейнстормлю

где такие задачи задают на каких олимпиадах?

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

Если кому интересно медленное решение: http://pastebin.com/FdACT6rG

Полным перебором сделал, чтоб было с чем сравнить ответ?

Такой вариант хорош (он хотя бы проще моего для понимания), но сложность та же - N^2 * logN.

Не полным, а то, что описано в первом посте. N^2 * logN, третью сторону бинарным делением. Чтобы сравнивать ответы. Ну и классический путь «перебор => оптимизации => просветление => реализация быстрого алгоритма». Вот на третьем этапе я застопорился.

Да ребята...

1) Сортируем отрезки.

2) Берем три самых длинных.

3) Если из них нельзя составить треугольник - самый длинный выкидываем, переходим к п. 2.

4) Считаем площадь s0 по Герону, запоминаем, самый длинный выкидываем и переходим к п2.

Как только площадь начала уменьшаться итерации думаю можно прекращать.

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

Ну то есть доказывать сейчас лень;-)

3) ... самый длинный выкидываем

Ты чего это?

Чего чего??? алгоритм...

Неоптимизированный:

cat heron.c 
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <sys/time.h>

#define SZ 100000

double heron(int a, int b, int c){
	double da=(double)a, db=(double)b, dc=(double)c;
	double p = da+db+dc;
	return sqrt(p*(p-da)*(p-db)*(p-dc));
}

int icmp(const void *a, const void *b){
	return *(int*)b-*(int*)a;
}

struct Triangles{
	int n1;
	int n2;
	int n3;
	double p;
} triangles[120];

int tricmp(const void *a, const void *b){
	struct Triangles ta = *(struct Triangles*)a;
	struct Triangles tb = *(struct Triangles*)b;
	return (int)(ta.p-tb.p);
}

int main(){
	int i, j, k, tri = 0;
	inline int test_tri(int a, int b, int c){
		float x = (float)a + (float)b;
		if(x < (float)c) return 0;
		if(abs(a-b) > c) return 0;
		return 1;
	}
	int *sides = malloc(SZ*sizeof(int)), *ptr;
	ptr = sides;
	srand(time(NULL));
	for(i=0; i < SZ; i++) *ptr++ = rand();
	qsort(sides, SZ, sizeof(int), icmp);
	for(i = 0; i < 10; i++){
		printf("sides[%d] = %d\n",i, sides[i]);
		triangles[tri].n1 = i;
		for(j = i + 1; j < 10; j++){
			triangles[tri].n2 = j;
			for(k = j + 1; k < 10; k++){
				triangles[tri].n3 = k;
				if(test_tri(sides[i], sides[j], sides[k])) triangles[tri].p = heron(sides[i], sides[j], sides[k]);
				else triangles[tri].p = -1.;
				tri++;
				if(tri > 120){printf("WTF?\n"); exit(-1);}
			}
		}
	}
	qsort(triangles, tri, sizeof(struct Triangles), tricmp);
	//for(i = 0; i < tri; i++) printf("%d: %.2f\n",i,triangles[i].p);
	printf("Max: triangle %d, %d, %d (S=%g)\n", sides[triangles[0].n1], sides[triangles[0].n2], sides[triangles[0].n3], triangles[0].p);
	free(sides);
}

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

Сдвиг можно тоже оптимизировать: если разница между младшими отрезками из предыдущей триады больше минимального - сдвигаем «окно» сразу на 2 отрезка.

Идея точно неправильна: на acmp есть аналогичная задача с мелкими ограничениями (до 1000, я ее давно решил медленным решением). Написал вашу идею - не проходит второй тест.

Упс, sorry:

s/ta.p-tb.p/tb.p-ta.p/

нужно же в обратном порядке сортировать

Можно словами?

Тривиальный факт - для увеличения площади уменьшать надо самую длинную сторону -> все три стороны должны лежать друг за другом. Так?

Я выше уже писал: сортируем в обратном порядке стороны, затем перебираем 10 самых больших, заполняя структуру {номера сторон, площадь} (если это - не треугольник, площадь = -1).

Затем полученные 120 треугольников сортируем в обратном порядке по площади. Самый первый и будет искомым.

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

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

если 2 стороны больше третьей, то площадь максимальна, если третья сторона длинее всех остальных третьих.

например для геометрической прогрессии 1,2,4,8, ... вообще ни один треугольник сложить нельзя.

хотя я написал какую-то чушь

> если 2 стороны больше третьей, то площадь максимальна, если третья сторона длинее всех остальных третьих.

Правильно, но при замене самой длинной стороны на сторону к-я меньше самой короткой площадь может возрасти.

Мысль с упорядочиванием однозначно верна (иначе эту задачу вообще решить нельзя). Дальше доказать, если стороны лежат в последовательности подряд, то все дост просто.

На первй взгляд да, но с четверотго прочтения я Вашу мысль понял;-)

Контрпример: 10 самых больших сторон подобраны так, чтобы из них нельзя было вообще построить треугольники. Например, 1000000, 2000000, 4000000 и т.д. до 1024000000.

Извиняюсь, ошибся с реализацией. Спасибо, легкий набор тестов проходит.

Так. Если же это уменьшит площадь - мы уже перелезли через пик и смысла продолжать нет.

Тяжелый тоже должно пройти - попробую.

Я о том и говорю;-)

#!/usr/bin/python
import sys

def S(l) : p = .5*sum(l); return ( p*(p-l[0])*(p-l[1])*(p-l[2]) )**.5

s0, L = 0, map( int, open(sys.argv[1]).readlines() )
L.sort()

while L :
    try : abc0 = L[-3:]; s0 = S(abc)
    except : L.pop(-1)

while len(L)>4 :
    L.pop(-1)
    try : abc1 = L[-3:]; s1 = S(abc1)
    except : break
    if s1>=s0 : s0, abc0 = s1, abc1
    else : break

print abc0, s0

Не тестировал.

Там 100000 сторон! Так что будем считать, что такой случай маловероятен.

Ну йеее.. Вам же привели пример. 1,1,1,2,4,8,... Ы?

А я и сказал, что сделал безо всяких математических обоснований. Если продумать все, как надо, то это уже явно будет не олимпиадная задачка.

Можно вообще свести все это к функциональному анализу...

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

PS. Я все-таки не люблю решать задачи эвристиками, которые связаны с фактором «авось повезет» - ибо на самом деле с вероятностью 99,99% таки не повезет.

На многих турнирах/олимпиадах, особенно коммандных, защитывается только полное решение.

А полное == проходящее все тесты, которых как минимум 20, и из них как минимум несколько специально подобраны, чтобы ломать qsort и эвристики, до которых додумались сами создатели задач.

ОК. Делаем по-другому: либо сначала выбрасываем все стороны, на которых нельзя построить треугольники; либо берем тот же алгоритм и, если после сортировки треугольников площадь первого == -1, переходим к следующей десятке, начиная с номера 8.

которых как минимум 20

Из серьезных олимпиад, где меньше тестов - только Всеукр - там у самой легкой задачи 10 тестов, а у средней и сложной ЕМНИП 20. Те, кто проводят ее, объясняют это тем, что участников много => не хватает ресурсов, чтобы быстро тестировать. И там ВСЕ тесты, кроме одного-двух - на лом эвристик.

Контрпример: реально существует только один треугольник, а оставшиеся 99997 сторон не могут образовать треугольники. Вырождается в самый сверх-неэффективный перебор (N^3).