ankeet's blog

By ankeet, history, 6 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ankeet (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ankeet (previous revision, new revision, compare).

»
6 years ago, # |
Rev. 7   Vote: I like it +3 Vote: I do not like it

You can compute the area of this ellipse portion directly by compressing the ellipse into a unit circle. Then it reduces to calculating the area of a circular segment plus a triangle. Solution.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I calculated the area of the ellipses, added them and finally did some inclusion-exclusion. But I did simple integration, not Simpson's I believe. You can take a look if you want.

Solution