State Fair: Difference between revisions

From programming_contest
Jump to navigation Jump to search
Newer edit →
imported>Kmk21
Created page with "This problem gives you a circle and the length of the "unique" edge of an isosceles triangle and asks you for the shortest the other legs must be such that the triangle enclos..."
 
imported>Kmk21
No edit summary
Line 8: Line 8:
It is impossible to satisfy all the constraints of the problem as written in all cases. Given that the output is a single number, we will assume that we can choose option 1.
It is impossible to satisfy all the constraints of the problem as written in all cases. Given that the output is a single number, we will assume that we can choose option 1.


Intuitively, we can see that the edges will all be tangent to the circle to get minimum distance. This means we just have to do some trig. Consider the midpoint of the given edge. Draw a line to the opposite angle. This will be a right triangle (due to isoscelese-ness) with the hypotenuse what we're trying to solve for. This length will be
## Solution 1 ##
Intuitively, we can see that the edges will all be tangent to the circle to get minimum distance. This means we just have to do some trig. Consider the triangle formed by the midpoint of the given edge (tangent to the circle...due to isoscelesness...remember tangent lines form right angles to the radius!), the center of the circle, and one of the angles of the triangle we are forming. We can use the pythagorean theorem to solve the length of the edge from the center of the circle to that angle.


<pre>x=sqrt((c/2)^2+(2r+y)^2)  # y is the distance between the circle and the intersection of the two similar edges</pre>
Now consider the tangent point of one of the "longer" sides. We can solve the distance from the angle from above to this point using pyth plus an edge drawn from the center to THIS tangent point.


We can create some other relations:
Lets call the edge length we're trying to solve for x, and the segment we just solved for as a, and the distance from the midpoint of the circle to the angle of the two similar sides as y. We can then form two similar triangles:
<pre>
c/2=x*cos(θ)
2r+y=x*sin(θ)
</pre>


But these don't really help....since they just prove the pythagorean theorem above. We need instead a relation involving the circle. We know that the point of contact between x and the cirlce is a right angle. So, we can have:
# c/2, r + y, x
# r, x-a, y


<pre>
We know c/2 and r, so we know the ratio of the other similar sides will follow. This gives us two equations (one for each of the two sides) with two unknowns (x and y), which we can solve for.
r^2+(r+y)^2=z^2 # z is length of x on the one side of the tangent point
</pre>
 
Even better, since these two triangles are similar (since they have 1 right angle, and share the angle of x and y, they are similar. Therefore:
 
<pre>
x/(c/2) = (r+y)/z

Revision as of 22:02, 29 December 2017

This problem gives you a circle and the length of the "unique" edge of an isosceles triangle and asks you for the shortest the other legs must be such that the triangle encloses the circle.

Note first that this question is ill-specified. It refers to the "shorter" side and longer "sides," but there is no guarantee in an isosceles triangle that the shorter side is the unique side. It doesn't state what to do in such a situation, as one could:

  1. actually optimize for minimal rope, and make the similar sides "shorter" than the unique side
  2. make the "shorter" side one of the similar sides, meaning there is only one longer "side"
  3. "stretch" the other two sides so that the unique side is still shorter, but this does not minimize rope.

It is impossible to satisfy all the constraints of the problem as written in all cases. Given that the output is a single number, we will assume that we can choose option 1.

    1. Solution 1 ##

Intuitively, we can see that the edges will all be tangent to the circle to get minimum distance. This means we just have to do some trig. Consider the triangle formed by the midpoint of the given edge (tangent to the circle...due to isoscelesness...remember tangent lines form right angles to the radius!), the center of the circle, and one of the angles of the triangle we are forming. We can use the pythagorean theorem to solve the length of the edge from the center of the circle to that angle.

Now consider the tangent point of one of the "longer" sides. We can solve the distance from the angle from above to this point using pyth plus an edge drawn from the center to THIS tangent point.

Lets call the edge length we're trying to solve for x, and the segment we just solved for as a, and the distance from the midpoint of the circle to the angle of the two similar sides as y. We can then form two similar triangles:

  1. c/2, r + y, x
  2. r, x-a, y

We know c/2 and r, so we know the ratio of the other similar sides will follow. This gives us two equations (one for each of the two sides) with two unknowns (x and y), which we can solve for.

Retrieved from "https://wiki.speedyguy17.info/index.php?title=State_Fair&oldid=1112"