| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| What shape is the football gate? | Nodir NAZAROV Komiljonovich | 1874. Футбольные ворота | 12 янв 2023 15:20 | 4 |
I tried to figure it out, how 1 tree and two sticks with the length of 2 can form the area more than 4? The largest area would be rectangle. What is the trick on this problem, can anybody explain with Geometry language.
Thanks. The key point of the problem statement is
"She knew that the standard football goal was rectangular, but, being creative, she assumed that her goal could have the form of an arbitrary quadrangle."
So, it may be not a rectangle. I tried trapezoid like:
/|
2/_|
| |
2|__|
x
and tried to maximize the function - f(x) for total area which answer is sqrt(3) and total area is ~4.33
How to get ~4.8 for the given test? Try placing sticks a and b as follows:
#
#`. a
# `.
# `.
x # \
# \ b
# \
# \
=====================
y
Hint: It can be proved that the area is maximal when x = y and angle between a and b is 135 degrees. |
| test case #27 | Choker | 1874. Футбольные ворота | 20 сен 2019 13:34 | 7 |
what is wrong with test #27 ? try 1 10000
answer 25007071.3178118650 25007071.3178118655 for 1 10000. Accurate enough, but still wrong answer on test case #27. In #27 system checks output format
I changed my python solution
print FLOATANS
to
print "%0.6f" % FLOATANS
and get AC
Edited by author 08.05.2013 14:10 I had wrong answer on test 27, but corrected it by using "long double" type
There's my code
[code deleted]
Edited by moderator 23.10.2019 22:04 |
| для тех, кто не знает геометрии | Vyacheslav Kim | 1874. Футбольные ворота | 1 авг 2018 00:37 | 3 |
Если вы такой же идиот в геометрии, как и я, то сделайте 2 вложенных тернарных поиска по углам и все пройдет :). Удачи FFFUUUU
This is a bad solution. There is just a formula for maximum area Nah. Ternary search on coordinates works well too |
| What shape is the football gate? | Nodir NAZAROV Komiljonovich | 1874. Футбольные ворота | 30 янв 2014 20:15 | 1 |
I tried to figure it out, how 1 tree and two sticks with the length of 2 can form the area more than 4? The largest area would be rectangle. What is the trick on this problem, can anybody explain with Geometry language.
Thanks.
Edited by author 30.01.2014 20:18 |
| Mathmatical solution | 198808xc | 1874. Футбольные ворота | 21 фев 2013 04:25 | 8 |
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? Write your e-mail.
I will help you. 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 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! 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). // 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. My solution and explanation gets about 5-7 lines of text :)It's so easy Can you post the mathematical explanation of your solution? |
| Mathematics behind the scene (proof) | KNIGHT0X300 | 1874. Футбольные ворота | 21 фев 2013 04:22 | 2 |
It is very tempting to start solving using angles. But I would advice you to start with distances from the origin along x and y directions (say x and y). Following steps should easily guide you to the answer.
1) Area = 1/2*(xy+ ab Sin(ArcCos([a^2+b^2-x^2-y^2]/[2ab])))
2) Using partial derivatives show x=y
3) substitute x=y in area and using first derivative of area show that
x^2= [a^2+b^2+sqrt(2)ab]/2
4) Substituting y=x and the result from (3) Area =[a^2+b^2]/4 + ab/sqrt(2)
Edited by author 08.02.2013 15:38 1)I can compute the partial derivative of the area function.
How do you prove that x=y
2)I can compute the derivative of the area function with x=y but how do you prove that
x^2= [a^2+b^2+sqrt(2)ab]/2
|
| Need help with prove | exwRabbits_AlMag(VNTU) | 1874. Футбольные ворота | 8 фев 2013 15:41 | 2 |
The key for solution was realizing that the ends of the sticks was on the same distance from origin. How to prove that?
I have a function F(angleA, angleB). I took derivatives dF/angleA and dF/angleB, they must be equal to zero. Then what? Refer to my new topic :)
Cheers |
| Ternary search works well | Alexey Dergunov [Samara SAU] | 1874. Футбольные ворота | 12 июл 2012 23:23 | 4 |
I thought that there will be presicion problems, but it turned out that ternary search works pretty well. There is a formula! It is so easy to find it using derivative! It is not so cool to solve this problem using ternary search! I tried but it was too difficult for me. Hmm, I spent about 3-5 minutes to find this formula :) |
| 1 Wrong | Fadeev.E.V | 1874. Футбольные ворота | 22 фев 2012 17:53 | 4 |
1 Wrong Fadeev.E.V 2 янв 2012 04:43 Please tell me why I wrong?
import java.util.*;
import java.math.*;
public class Program {
public static void main (String arqs[]) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt(),b = sc.nextInt();
double x = (a+Math.sqrt(a*a+2*b*b))/2;
double S = (a+x)/2*Math.sqrt(b*b-(x-a)*(x-a));
System.out.printf("%.9f",S);
}
}
Edited by author 02.01.2012 04:44 Hi,
Can you please tell me how did you find this formula ?
I have tried many times, but cannot find the solution.
Thanks. Oh, all is very easy. Using derivative, you can find angle between sticks in which area has a maximum value. Just find stationary point of area function.
Edited by author 12.02.2012 17:45 |
| Need a help | Islam | 1874. Футбольные ворота | 30 окт 2011 17:12 | 2 |
Please, can anybody tell how to solve this problem, which algorithm is used, how could the answer of sample test be 4.828427125? maybe a maximum of (2xy+x*sqrt(a*a-x*x)+y*sqrt(b*b-y*y))/2 should do |
| Precision | budbud | 1874. Футбольные ворота | 22 окт 2011 15:54 | 2 |
"The answer must be accurate to at least six fractional digits."
Edited by author 22.10.2011 15:54 |
