Mathmatical solution

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

Write your e-mail.

I will help you.

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

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

My solution and explanation gets about 5-7 lines of text :)It's so easy

Re: Mathmatical solution

Can you post the mathematical explanation of your solution?