Smoothed Gardens

From programming_contest
Jump to: navigation, search

This problem asks us to find the area enclosed by a a certain given technique.

By inspection, we see that the boundary is broken up into 6 segments, each an ellipsis segment. 3 of them are centered over the sides, using the two endpoints as the foci. The other 3 are centered over the corners, with the foci the endpoints of the OPPOSITE side. One can see the six ranges clearly by extending the edges of the triangle infinitely in either direction. We will compute the area of each of these 6 regions separately, and then add in the area of the triangle itself.

The first 3 are "trivial" as the center of the ellipse is the center of the matching side. We then have to calculate the angle to each of the "endpoints" of the ellipsis segment (where it would contact the line coincident with one of the triangle's other sides), and then apply the ellipsis segment area algorithm to calculate it.

How to do that?

Well, ultimately we'll have to integrate over the angle, where each infintesimal area is the area of the sector of a circle with radius=r(θ)

the former is given by:

r(θ)=ab/sqrt((a*sin(θ))^2 + (b*cos(θ))^2) (can be seen as a circle stretched first in the a direction, and then in the b direction).

The second is given by some trig

r*d(θ)/2*pi

Substituting r(θ) into the equation above and computing the definite integral for the appropriate angles gives the area swept by that angle range and bounded by the ellipsis.

Note in our drawing that this is not the total area of this "region, since there are triangles formed by the center point of the edge, the endpoint of the edge, and the intersection of the boundary and the extended line from the other edge which is not covered in the sweep. Be sure to add in that part. Note that it is a definite integral, so we don't have to explicitly calculate it...but to simply make our step size small enough to get enough precision.

The other 3 ellipses, centered over the angles with foci on the opposite edges, are much more challenging. Computing the area is simple, but the issue is the areas overlap with each other, along with the areas calculated in the first part. We have to do a significant bit of trig to ensure those areas are subtracted out. Ultimately, for this part, we want ONLY the area formed between the triangle "angle" and the boundary itself. We will have to subtract out the area which lies within the triangle itself, along with the area that lies in one of the 3 previously calculated regions.

Lastly, we add in the area of the triangle itself and print to 2 digits of precision.