Матч
353, Покрытие эллипса (EllipseCoverage)
Дивизион 2,
Уровень 1
Эллипсом называется фигура на
плоскости, сумма расстояний от любой точки которой до двух заданных является
постоянной. Эти две фиксированные точки называются фокусами. По координатам
фокусов (x1, y1), (x2, y2)
и сумме расстояний от точек эллипса до фокусов d найти количество точек с целочисленными координатами, лежащих
строго внутри эллипса.
Класс: EllipseCoverage
Метод: int
calculateCoverage(int x1, int y1,
int x2, int y2,
int d)
Ограничения:
-100 £ x1, y1, x2, y2 £ 100, 1 £ d £ 200.
Вход. Координаты фокусов (x1,
y1), (x2, y2)
и сумма расстояний от точек эллипса до фокусов d.
Выход. Количество точек с целочисленными координатами, лежащих
строго внутри эллипса.
Пример входа
|
x1 |
y1 |
x2 |
y2 |
d |
|
0 |
0 |
0 |
0 |
4 |
|
-3 |
0 |
3 |
0 |
10 |
|
10 |
12 |
8 |
14 |
50 |
Пример выхода
9
59
1941
РЕШЕНИЕ
перебор + геометрия
С учетом заданных в условии
задачи ограничений следует, что внутри эллипса могут находиться точки с
целочисленными координатами (x, y), для которых -200 £ x, y £ 200. Перебираем все такие точки, вычисляем сумму расстояний от них до
фокусов эллипса. Если полученное расстояние меньше d, то точка (x, y) лежит внутри эллипса. Подсчитываем
количество таких точек.
ПРОГРАММА
#include <stdio.h>
#include <math.h>
class EllipseCoverage
{
public:
int calculateCoverage(int
x1, int y1, int
x2, int y2, int
d)
{
int x, y, res = 0;
for(x = -200; x <= 200; x++)
for(y = -200; y <= 200; y++)
{
double dist = sqrt(1.0 * (x-x1) * (x-x1)
+ (y-y1) * (y-y1)) +
sqrt(1.0 * (x-x2) * (x-x2) + (y-y2) * (y-y2));
if (dist < d) res++;
}
return res;
}
};