Газон

В случае менее жестких ограничений на размеры газона или радиуса полива задача была бы намного проще. Можно было бы, например, пробежаться по всем пучкам травы газона, проверяя каждый из них на достижимость струей дождевальной установки и в случае успеха увеличивать значение некоторой переменной-счетчика. Однако число таких пучков в нашей задаче может быть более 10¹⁰, что невыполнимо для простого перебора, даже если сузить площадь поиска пучков и пробегать только по всем политым.

Пусть (X₁,Y₁) - левый нижний угол газона, а (X₂,Y₂) - верхний правый. Заметим, что это не обязательно именно так, т.к. в условиях порядок задания противоположных углов газона не оговорен, но если это не так, то несложно эти координаты привести именно к такому виду. Мы можем сократить площадь поиска следующим образом: политые пучки травы не могут быть левее газона и левее круга полива, поэтому нас будут интересовать только те пучки, которые находятся не левее чем max(X₁, X₃ - R), аналогичное мы можем сказать о правой, нижней и верхней границах. Таким образом, определен новый прямоугольник поиска, в котором все еще много точек. Далее, будем перебирать всевозможные координаты по X, вычисляя количество политых пучков травы, которые находятся в X-ой координате. Для этого вовсе не обязательно пробегать по всем значениям Y. Используя теорему Пифагора, мы можем определить границы пересечения вертикальной прямой X с окружностью, ограничивающей зону полива, так мы определим отрезок координаты X, принадлежащей кругу полива. Определение отрезка, принадлежащего газону представляет из себя простую задачу, а пересечение найденных выше отрезков - это и есть количество точек в координате X, которые требуется посчитать. Так мы получили линейный алгоритм относительно ширины газона и радиуса круга полива.

Изложенную выше идею можно записать так:

  read(x1,y1,x2,y2,x3,y3,r);

  sum=0;
  for x = max(x3-r,x1) .. min(x3+r,x2){
    t = int(sqrt(r*r-(x3-x)*(x3-x)));
    t = min(y2,y3+t) - max(y1,y3-t)+1;
    if(t > 0) sum = sum+t;
  }

  write(sum);

В процессе реализации программы следует правильно выбирать типы данных: можно обойтись целыми типами, не забыв для переменной накопления суммы использовать 8-байтовое целое. Так же в различных языках программирования могут возникать различные сложности, связанные с вычислением корня и округлением, поэтому и здесь нужно сделать все аккуратно.

[Обсуждение] [Все попытки] [Задача]