TopCoder problem "EllipseCoverage" used in SRM 353 (Division II Level One)



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
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.
1)
    
-3
0
3
0
10
Returns: 59
Be careful with (0, 4), (-5, 0), (0, -4) and (5, 0).
2)
    
10
12
8
14
50
Returns: 1941
3)
    
0
0
0
0
200
Returns: 31397
4)
    
13
-23
49
91
200
Returns: 25187

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7839

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10710&pm=7839

Writer:

xOberon

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Geometry, Simple Math