State Fair

From programming_contest
Revision as of 21:14, 29 December 2017 by 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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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.

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

x=sqrt((c/2)^2+(2r+y)^2)  # y is the distance between the circle and the intersection of the two similar edges

We can create some other relations:

c/2=x*cos(θ)
2r+y=x*sin(θ)

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:

r^2+(r+y)^2=z^2 # z is length of x on the one side of the tangent point

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:

x/(c/2) = (r+y)/z