ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1874. Футбольные ворота

Mathmatical solution
Послано 198808xc 27 янв 2012 14:22
From the sample test and the test on board (a = 10000 and b = 1), I have worked out the solution by guessing, and ACed online.

For input a and b, the solution is:
(a ^ 2 + b ^ 2) / 4 + Sqrt(2) * a * b / 2

However, I could not find the proof for this.

Any help or suggestion for me?
Re: Mathmatical solution
Послано Neofit 27 янв 2012 20:37
Re: Mathmatical solution
Послано Anatoly 30 янв 2012 14:13
S = F(alfa, betta), where alfa is angle of stick a, and betta is angle of stick b. It it requirement for extremum of such function that both partial derivatives (dS/dalfa and dS/dbetta) is zeros. From these two equations you could find that angle between a and b is constant, regardless of their lengthes.
Using new formula and getting it's derivative, it's quite simple to show that length from zero point to touching point between stick and tree and length between zero point and touching point between 2nd stick and ground is equal.
Also we know hypotenuse of this rectangular isosceles triangle because we know a, b and angle between.
S = sum of S of two totaly determined triangles and it is exactly the formula you wrote.

Edited by author 30.01.2012 14:21
Re: Mathmatical solution
Послано 198808xc 30 янв 2012 16:56
Thanks so much, to both Neofit and Anatoly.
I have followed the ideas of Anatoly, and finished the proof.

This is really a good geometric problem!
Re: Mathmatical solution
Anatoly, could you explain how sticks should been placed in task example? I even couldn't imagine how to place 2 sticks to get total square more than 4 (rectangle).
Re: Mathmatical solution
Послано -XraY- 8 сен 2012 22:27
// S(x, a, b) + x * x / 4 max.
// sqrt((x + a + b) * (x + a - b) * (x + b - a) * (a + b - x)) + x * x
// 2*x + 1/2 * (-2x * (x * x - (a-b) * (a-b)) + 2x * (-x * x + (a+b) * (a+b))) / sqrt(...) = 0
// 2*x + (-x * (x * x - (a-b) * (a-b)) + x * (-x * x + (a+b) * (a+b))) / sqrt(...) = 0
//     delete x
// 2 + (2*(a*a + b*b) - 2*x*x) / sqrt(...) = 0
// 1 + ((a*a + b*b) - x * x) / sqrt(...) = 0
//   x^2 - (a^2 + b^2) = sqrt(...)
// (x^2 - (a^2 + b^2)) ^ 2 = (x ^ 2 - (a - b) ^ 2) * ((a + b) ^ 2 - x ^ 2)
// y = x^2
// (a*a + b*b))^2 - 2*(a*a + b*b) * y + y*y = -y*y + (2*(a*a + b*b)) * y - (a*a - b*b) ^ 2
// 2*y*y - 4*(a*a + b*b)*y + 2*(a^4 + b^4) = 0
// y^2 - 2(a^2 + b^2)y + (a^4 + b^4) = 0
// D/2 = 2(ab)^2
// y = (a^2+b^2 (+-) ab*sqrt(2))
// Smax = (2y - (a^2+b^2)) / 4 = (a^2+b^2)/4 + ab/sqrt(2)
printf("%.18lf\n",  (a * a + b * b) / 4 + (a * b) / sqrt(2.0));

it's the part of my solution and explanation of this formula.
Re: Mathmatical solution
Послано Andrew Sboev [USU] 8 сен 2012 23:45
My solution and explanation gets about 5-7 lines of text :)It's so easy
Re: Mathmatical solution
Послано TinyJanssen 21 фев 2013 04:25
Can you post the mathematical explanation of your solution?