EllipseCoverage | Topcoder Archive

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.

Definition

Class:: EllipseCoverage
Method:: calculateCoverage
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int calculateCoverage(int x1, int y1, int x2, int y2, int d)
(be sure your method is public)

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.

Examples

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.