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
7
-9
2
-4
20
Returns: 296
0
3
-8
5
18
Returns: 221
-3
-10
5
-2
18
Returns: 193
1
4
1
10
10
Returns: 59
6
-5
-2
-7
18
Returns: 221
2
3
-10
-9
18
Returns: 85
-2
-3
-6
9
20
Returns: 237
-8
2
-8
-6
16
Returns: 167
-9
8
-1
-4
16
Returns: 85
-5
-3
3
-3
16
Returns: 167
-75
37
-43
-93
134
Returns: 597
-14
24
77
-74
189
Returns: 19822
99
68
75
-90
164
Returns: 4725
83
-15
41
-82
181
Returns: 23148
53
-76
90
16
147
Returns: 12522
-84
84
-76
72
16
Returns: 85
-33
30
32
5
90
Returns: 4028
-57
97
-60
32
68
Returns: 1058
-52
60
-40
94
50
Returns: 1359
62
-25
90
-89
92
Returns: 4319
36
38
76
-36
190
Returns: 25427
41
-1
-1
36
69
Returns: 2190
-100
-24
-65
-64
163
Returns: 19730
-95
30
-20
-27
143
Returns: 12092
41
-3
-58
93
168
Returns: 12668
-45
98
-12
49
74
Returns: 2590
-11
-30
27
26
135
Returns: 12387
55
-88
54
-54
148
Returns: 16732
80
-45
-4
-71
103
Returns: 4331
-42
58
-45
-93
167
Returns: 9352
100
99
100
100
200
Returns: 31392
-100
0
-99
0
200
Returns: 31392
-100
-100
-100
-100
200
Returns: 31397
-100
-100
-100
-99
200
Returns: 31392
100
100
100
100
200
Returns: 31397
100
100
100
100
10
Returns: 69
-100
0
-100
0
190
Returns: 28333
29
88
-99
0
200
Returns: 19775
-100
-100
-100
0
200
Returns: 27195
99
99
100
100
200
Returns: 31428
-100
-100
-100
-100
100
Returns: 7825
-2
-1
-2
-1
1
Returns: 1
50
60
51
61
10
Returns: 78
100
100
99
99
100
Returns: 7860
-100
-100
-100
-95
10
Returns: 70
50
50
50
50
50
Returns: 1941
-20
-20
20
20
200
Returns: 30099
-100
-100
-100
-100
10
Returns: 69
13
-23
-49
-91
200
Returns: 27893
1
0
-1
0
200
Returns: 31397
-100
-100
1
1
200
Returns: 21972
100
100
100
99
10
Returns: 78
-100
0
-100
0
100
Returns: 7825
50
50
50
0
101
Returns: 6955
-4
-1
0
0
100
Returns: 7848
100
100
100
100
1
Returns: 1
99
99
99
99
3
Returns: 9
10
99
10
-99
199
Returns: 3081
-100
50
-100
49
100
Returns: 7856
16
16
16
16
1
Returns: 1
100
100
100
100
20
Returns: 305
-100
-100
-100
-100
5
Returns: 21