сайт учителя информатики

Региональный этап Всероссийской олимпиады школьников по информатике 2008/2009 учебного года
Первый тур

Задача 2. Газон

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

Формат входных данных

В первой строке входного файла содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000).

Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)

Формат выходных данных

В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.

Пример входных и выходных данных

Иллюстрация к примеру

Краткие методические рекомендации по решению задачи

Одно из возможных решений данной задачи заключается в следующем. Для каждой прямой, содержащей все пучки травы с равной координатой по оси абсцисс (аналогично можно рассматривать и ось ординат), найдем ее точки пересечения с окружностью, отображающей область действия поливальной установки, если, конечно, такие точки существуют. Получив данные точки, не сложно за время O(1) посчитать количество пучков травы на данной прямой одновременно и политых, и постриженных. Это делается с помощью операции вычисления целой части числа. Далее, просуммировав найденные числа для всех прямых, можно найти ответ на поставленную задачу.

Не сложно показать, что время работы рассматриваемого решения будет O(r).

Возможные ошибки

Можно применить "лобовое" решение, т.е. создать два или  три массива, но на самом деле нужен только один размером 100 элементов. При лобовом решении необходим массив в 100000 элементов, а создать его в Turbo Pascal не удастся. Самое интересное, что лобовое решение проходит если использовать компилятор Free Pascal.

Текст программы на Паскале:

var 
  x1, y1, x2, y2, x3, y3, x: longint; 
  k, r, y: int64;
function kol(x, z1, z2: longint): longint;
  var      min, max, k: longint;
  begin
    if (x < x1) or (x > x2) or (z1 > y2) or (z2 < y1) then 
      k := 0 
    else 
      begin
        min := y1; 
        if z1 > y1 then 
          min := z1; 
        max := y2; 
        if z2 < y2 then 
          max := z2;
        k := max - min + 1
      end;
     kol := k
  end;
begin
  assign(input, 'lawn.in');  reset(input);
  assign(output, 'lawn.out');  rewrite(output);
  readln(x1, y1, x2, y2);
  read(x3, y3, r); 
  k := kol(x3, y3-r, y3+r); 
  y := r;
  for x := 1 to r - 1 do 
    begin
      while sqr(x) + sqr(y) > sqr(r) do 
        y := y - 1;
      k := k + kol(x3 + x, y3 - y, y3 + y) + kol(x3 - x, y3 - y, y3 + y)
    end;
  k := k + kol(x3 + r, y3, y3) + kol(x3 - r, y3, y3);
  write(k); 
  close(input);
  close(output);
end.