Подразделы

Другие разделы

Дата и время

16/11/2024 17:13:18

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

print2. Газон

Задача средней сложности, на эффективный алгоритм.
Простая проверка всех точек прямоугольника по отдельности на попадание в круг не эффективна, необходимо добавлять точки отрезками. Для этого рассматриваем все `x`, которые попадают в область пересечения, и находим минимальную и максимальную ординаты точек с выбранным `x`. К результату добавляем `y_max-y_min+1`.
var res:int64; { ответ может быть больше, чем 2*10^9 }
...
  res:=0;
  for x:=max(x1,x3-r) to min(x2,x3+r) do
  begin
    d:=trunc(sqrt(sqr(extended(r))-sqr(extended(x3-x))));
    ymin:=max(y1,y3-d);
    ymax:=min(y2,y3+d);
    if ymin<=ymax then
      res:=res+ymax-ymin+1;
  end;
Перед возведением в квадрат число преобразуется в вещественное, чтобы избежать переполнения. Функции max и min вычисляют максимум и минимум из двух чисел.
loading