This difficult geometry problem was given at last year's ACM GNYR. The task is quite interesting: you are given the coordinates of three stakes in the ground, and the length L of a string. You pull the string taut around the 3 stakes, and then sweep the string around the 3 stakes (similar in the way a regular 2-foci ellipse is constructed, but different than an n-ellipse). You end up with a simple closed curve, whose area you want to determine.
Does anyone have any ideas about solving this? My initial thought was to sample many points on the curve and then use shoelace for the area, and this probably would have worked given that only 2 decimal digits of accuracy are required, and that the official test cases were pretty weak. However, I did not find an easy way to sample the points.
The official solution splits the curve into portions of 6 "regular" ellipses, and then uses Simpson's rule to compute their areas. This seems very tedious, and extremely prone to bugs. I'm thinking there should be something much simpler, but I could not come up with anything.
