ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1874. Football Goal

Mathmatical solution
Posted by 198808xc 27 Jan 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
Posted by Neofit 27 Jan 2012 20:37
Re: Mathmatical solution
Posted by Anatoly 30 Jan 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
Posted by 198808xc 30 Jan 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
Posted by -XraY- 8 Sep 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
Posted by Andrew Sboev [USU] 8 Sep 2012 23:45
My solution and explanation gets about 5-7 lines of text :)It's so easy
Re: Mathmatical solution
Posted by TinyJanssen 21 Feb 2013 04:25
Can you post the mathematical explanation of your solution?