eolymp

Пятерка за неделю 1

Круг

   Данная задача является хорошим примером для поиска путей оптимизации алгоритма и может быть использована преподавателями на занятиях кружка именно с этой целью.
Попробуем данную задачу решить “в лоб”, то есть прямым перебором. Понятно, что нам необходимо учитывать все точки, которые имеют X иY координаты от –R до R и при этом расстояние от них до центра окружности (точки 0, 0) не превышает R. Пусть k – искомое количество таких клеток.

   На школьном алгоритмическом языке этот фрагмент можно написать, например, так:


k := 0;
для X от –R до R шаг 1
нц
для Y от –R до R шаг 1
        нц
   если X*X  + Y*Y <= R*R
    то k := k+1
   все
        кц
кц

   Сложность предложенного алгоритма составляет O(N^2).

   Реализация этого подхода на любом из языков программирования сразу покажет нам, что у нас идет значительно превышение по времени.
   Внимательно посмотрим на алгоритм, и поищем пути уменьшения вычислений.
   Сразу бросается в глаза, что мы постоянно вычисляем квадрат радиуса, а он для каждого случая остается неизменным, поэтому логично предположить, что его желательно вычислить до циклов. Итак, первый шаг оптимизации:


k := 0;
R2 := R*R;
  // квадрат радиуса обозначим R2
для X от –R до R шаг 1
нц
для Y от –R до R шаг 1
        нц
   если X*X  + Y*Y <= R2
    то k := k+1
   все
        кц
кц

   Внеся необходимые исправления в программную реализацию, мы по-прежнему на некоторых тестах получим TL. Причину мы уже знаем и присмотревшись более внимательно к алгоритму, можно заметить, что мы все ещё продолжаем делать лишние вычисления: во внутреннем цикле координата X при изменении Y не изменяется, поэтому это вычисление можно вынести за пределы внутреннего вложенного цикла по Y. Итак, получим:


k := 0;
R2 := R*R;
// квадрат радиуса обозначим R2
для X от –R до R шаг 1
нц
X2 := R*R;
// квадрат координаты X обозначим X2
        для Y от –R до R шаг 1
        нц
   если X2  + Y*Y <= R2
    то k := k+1
   все
        кц
кц

   Несмотря сделанные шаги по оптимизации сложность алгоритма по-прежнему остается O(N^2), и по прежнему мы не вкладываемся во временные рамки.

   А можно ли еще более оптимизировать алгоритм решения задачи? Конечно можно, ибо нет предела в стремлении к совершенству. Для этого нам нужно нарисовать рисунок на листочке в клеточку и более внимательно к нему присмотреться. Желательно вспомнить, что мы делаем, когда приносим домой арбуз или дыню. Правильно, разрезаем на более мелкие части!

   Можно заметить, что наш нарисованный круг можно разрезать на 2 половинки, а еще более внимательные сразу скажут, что лучше разрезать на 4 части таким образом, чтобы захватывать при этом только 1 координатную полуось. При этом не учтенной остается только одна точка в центре круга, которую нужно не забыть в конце прибавить.

   Итак, творческий поиск привел к следующей реализации алгоритма:


k := 0;
R2 := R*R;
  // квадрат радиуса обозначим R2
для X от 1 до R шаг 1
нц
X2 := R*R;
// квадрат координаты X обозначим X2
        для Y от 0 до R шаг 1
        нц
   если X2  + Y*Y <= R2
    то k := k+1
   все
        кц
кц
k := 4*k + 1;


   Ура! Реализация на конкретном языке программирования приводит к долгожданному АС, но особого чувства радости это почему-то не вызывает, так как в процессе сдачи мы уже успели заметить, что существуют решения, работающие намного быстрее нашего и очень хочется оптимизировать наш алгоритм дальше, тем более что сложность нашего “оптимизированного” алгоритма по прежнему O(N^2).
   
   Предлагаем сделать это самостоятельно, дав при этом небольшую подсказку: нужно сделать алгоритм линейным, т.е. избавиться от одного из циклов. Именно самостоятельная находка этого алгоритма даст возможность легко решить и следующую задачу – “Закрашенные клеточки 2”.

Закрашенные точки

   Эта задача на формулу Пика (или Пике, такое написание фамилии ученого, открывшего этого формулу, также встречается иногда в литературе). Формула справедлива только для многоугольников, вершины которых находятся в точках с целочисленными координатами.

   Эту формулу легко можно найти в Интернете, например в той же Википедии: http://ru.wikipedia.org.  Пусть S – площадь треугольника, G – количество точек с целочисленными координатами внутри треугольника, N – количество точек с целочисленными координатами на ребрах треугольника. Тогда:

  S = G + N/2 ¬ 1 (формула Пика)

   Выведем из неё нужную нам формулу:

   G = S – N/2 + 1
   N = N1 + N2 + N3, где N1 – количество целочисленных точек  на одном ребре, N2  - на втором и  N3 – на третьем. Так как концы отрезков нами учитывались повторно, нужно не забыть вычесть повторно посчитанные вершины из полученного ответа.

   Площадь треугольника можно найти разными способами, например по формуле Герона, или обобщенной формуле нахождения площади многоугольника, базирующемся на понятии ориентированных площадей...

   Для нахождения количества  точек, лежащих на сторонах треугольника, можно воспользоваться алгоритмом, который применяется при решении задачи “Отрезок” (http://e-olimp.com/problems/136).

Зеленое пятно - 2

   Задача “Зеленое пятно 2” является не очень сложной, однако предложенная нами категории сложности на контесте связана с тем, что для ее решения необходимы специфические знания, которые, впрочем, не выходят за рамки школьного образования.

   Опишем словесно-формально алгоритм решения данной задачи.

   Для начала нам необходимо научиться находить количество точек пересечения 2-х окружностей и их взаимное расположение. В этом вам поможет задача с портала “Две окружности” (http://e-olimp.com/problems/4), где именно это и требуется найти.

   Обозначим через d расстояние между центрами окружностей. R1 – радиус одной окружности, а R2 – другой, причем R1 <= R2.

   Далее понятно, что если одна из окружностей находится внутри другой (R1 + d <= R2), то площадь зеленого пятна равна площади окружности меньшего радиуса, если окружности совпадают – площади любой из них (впрочем, этот случай можно включить в предыдущий). Если окружности соприкасаются (d = R1 + R2), или центры окружностей находятся на расстоянии, большем суммы их радиусов, площадь также равна нулю.

   Наиболее интересен случай, когда окружности частично пересекаются, однако он также не предоставляет особой сложности, так в этом случае можно, например, находить искомую площадь, как сумму площадей 2-х сегментов.

   Из курса школьной математики известно, что найти площадь сегмента можно, например, как разность площади сектора и равнобедренного треугольника, построенного на радиусах окружностей и отрезке, соединяющем 2 точки пересечения окружностей.

   Впрочем, существуют и другие, также чисто математические способы определения этой площади.

   Подводя итоги выше сказанному, можем перефразировать одну широко известную фразу: “Математика – царица всех наук и служанка информатики…”   :idea: