EllipseCoverage
SRM 353 · 2007-06-07 · by xOberon
Problem Statement
An ellipse is a figure on a plane where the sum of the distances from any point on its perimeter to two fixed points is constant. The two fixed points are called foci (plural of focus). In this problem we are interested in the number of points with integral coordinates that lie strictly inside of the given ellipse.
The foci are (x1, y1) and (x2, y2), and the fixed sum of distances is d.
Constraints
- x1, y1, x2, y2 will be between -100 and 100, inclusive.
- d will be between 1 and 200, inclusive.
- The arguments will define a valid ellipse with positive area.
0 0 0 0 4 Returns: 9
This is a circle with radius 2. The points (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0) and (-1, 1) lie strictly inside the circle. The points (-2, 0), (0, -2), (0, 2) and (2, 0) are on the perimeter, so they do not lie strictly inside the circle and should not be counted.
-3 0 3 0 10 Returns: 59
Be careful with (0, 4), (-5, 0), (0, -4) and (5, 0).
10 12 8 14 50 Returns: 1941
0 0 0 0 200 Returns: 31397
13 -23 49 91 200 Returns: 25187
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllipseCoverage with a public method int calculateCoverage(int x1, int y1, int x2, int y2, int d) · 67 test cases · 2 s / 256 MB per case