Очень трудная задача с геометрией...

[bananasus]

Народ, помогите пожалуйста с задачей. Уже голову сломал, решая её... Тут стопудова все очень легко, а я хожу вокруг да около и не могу догнать.
Вот задача:

Определить координаты вершин прямоугольника наименьшего периметра , содержащего треугольник , координаты вершин которого (x1,y1), (x2,y2)(x3,y3).

Вот часть решения:

#include "stdafx.h"
#include <stdio.h>
#include <math.h>
int main()
{
	int x1,x2,x3,y1,y2,y3;
	float a,b,c,P1,P2,P3,ha,hb,hc,p;
	scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
		a = sqrt( (float)((x2-x1)*(x2-x1) + (y1-y2)*(y1-y2)) );
		b = sqrt( (float)((x3-x2)*(x3-x2) + (y3-y2)*(y3-y2)) );
		c = sqrt( (float)((x3-x1)*(x3-x1) + (y1-y3)*(y1-y3)) );
		p = (a+b+c)/2;
		ha = 2*( sqrt(p*(p-a)*(p-b)*(p-c)) )/a;
		hb = 2*( sqrt(p*(p-a)*(p-b)*(p-c)) )/b;
		hc = 2*( sqrt(p*(p-a)*(p-b)*(p-c)) )/c;
		P1 = (ha+a)*2;
		P2 = (hb+b)*2;
		P3 = (hc+c)*2;
	return 0;
}

Трудность заключается в определени координат прямоугольника. Получается так, что координаты 2-х вершин уже известны, остается найти еще 2. А вот как, ума не приложу. Тут надо наверное от векторов плясать.

[Abstraction]

Любой прямоугольник, описанный вокруг треугольника, можно задать числом 0<=t<=1. При этом, tx+(√1-t²)y=a, (√1-t²)x-ty=b - уравнения прямых границ; подставляя вершины треугольника, для каждого из уравнений можно найти минимальное и максимальное значение a и b, после чего минимизировать сумму разностей между минимумами и максимумами a и b перебором t (т.е. функция p(t) вычислима и имеет минимум).
В Ваших вычислениях Вы, по всей видимости, исходите из предположения, что у оптимального прямоугольника одна из сторон совпадает со стороной треугольника, а я не уверен, что это верно.

[bananasus]

Неужели больше нет идей?

[Son Of Pain]

Тебе уже сказали решение. Какие еще идеи нужны?

[Serge_Bliznykov]

Abstraction, признаюсь, для меня Вами математические выкладки оказались чуть сложноваты, не исключено, что для автора темы - тоже...
Если Вы их чуть-чуть "разжуёте", думаю, что автору будет чуть проще в них разобраться.


ну и ещё, уже мне чисто любопытно.

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

может не совпадает по длине, но находится на одной линии?.. дело в том, что я нарисовал несколько абстрактных треугольников и попытался их "заключить" в минимальный прямоугольник. Мне показалось, что логичным сделать предположение, что одна из сторон треугольника лежит на одной прямой с оптимальным прямоугольником...
я ошибаюсь? можно примерчик (схему или координаты), когда это не так?..

[Abstraction]

Мне показалось, что логичным сделать предположение, что одна из сторон треугольника лежит на одной прямой с оптимальным прямоугольником...

Мне тоже так кажется, но вот доказать не получается. Отсюда и более общий способ.

Прямоугольник однозначно определяется направлением одной из прямых-продолжений сторон (возьмите сами треугольник и направление прямой, и увидите, что прямоугольник по этим данным строится однозначно). Из прямых, можно ограничиться прямыми с положительным наклоном - они задаются углом α с осью OX. Уравнение прямой при этом будет sinα*x+cosα*y=const; уравнение перпендикулярной прямой - cosα*x-sinα*y=const. При этом, при заданном α, для каждой из вершин треугольника можно вычислить обе константы, получаем три значения для одной и три для другой. Максимум и минимум в каждой тройке соответствуют уравнениям прямых, на которых лежат границы прямоугольника, а разность максимума и минимума - расстояние между этими прямыми. То есть, для каждого α можно вычислить значение периметра P(α). Осталось, для удобства вычислений, заменить sinα на t и искать минимум P(t) при 0<=t<=1.