Wataru

Как найти угол на компьютере? Как его вообще можно вычислить? Очень редко в задаче можно выразить угол через какие-то другие известные углы в градусах. Чаще всего у вас есть какие-то координаты каких-то точек.

Из координат можно найти все тригонометрические функции - косинус, синус, тангенс... Из них потом уже можно получить значение угла в градусах/радианах через обратные тригонометрические функции, например арктангенс (atan в решении). Она по определению возвращает угол если ей передать значения арктангенса.

Чаще всего используют именно арктангенс, потому что, в отличии от косинусов/синусов, он хорошо работает для любого угла (у арксинуса, например, невозможно различить 45 и 135 градусов - значение синуса одно и то же). У арксинуса и арккосинуса нужно добавлять какие-то проверки сверху для решения неоднозначностей.

Почему в задаче такой ответ? atan() передаются косинус и синус угла, возможно растянутые на один и тот же коэффициент. Координаты точки М - (1/2 AB, 1/2 BC), ведь это середина AC. Представьте перпендикуляр из точки М на ость OX(BC). В получившемся треугольнике будет прямой угол, гипотенуза BM и катеты с длинами 1/2 AB, 1/2 BC. Соответственно, косинус/синус искомого угла будут 1/2/AM*AB, 1/2/AM*BC. Теперь вспоминаем, что atan() можно передавать значения, умноженные на константу. Вот пусть константа будет 2/AM. Тогда остаются AB и BC.

Еще, можно смотреть на atan() так - передайте ему координаты конца вектора и он вернет угол между OX и вектором.

Это производная комбинации: (f(g(x)))' = f'(g(x))*g(x).

В вашем случае f(z) = z^2, g(w)=y-w*x.

f(g(w)) = f(y-w*x) = (y - w*x)^2

f'(z) = 2z, g'(w) = -x

Подставляем в первую формулу:
2(y - w*x)*(-x) - ровно то, что написано в книге.

Это задача о рюкзаке.

Решение через динамическое программирование:

int Count(vector<int> coins, int n) {
  vector<int> cnt(n+1, 0);
  cnt[0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int coin : coins) {
      if (i+coin <= n) cnt[i+coin] += cnt[i];
    }
  }
  return cnt[n];
}

Это известная задача иосифа. По ссылке есть всякие решения. Вам подойдет самое тупое и медленное. У вас в задаче k прибито гвоздями к 2.

Понять те формулы можно примерно так. Съели мы первый куст, перешли ко второму. Теперь перенумеруем их, что останется? Та же самая задача, только с n-1 кустом. Только все кусты сдвинуты на k позиций и один номера у них на один уменьшены. Т.е. можно взять тот самый куст который при n-1 останется и найти, какой у него был номер до сдвига.

Это обобщение известной задачи, где пропущено одно число. Там можно, например, вычесть все числа из n(n+1)/2. Или про-xor-ить все числа от 1 до n и все числа в массиве.

Для двух чисел нужно составить какие-то 2 уравнения, Например, найдите сумму двух чисел и сумму их квадратов: Сумма пропущенных чисел - это n*(n+1)/2 - (сумма всех чисел в массиве). Здесь надо аккуратно не забыть о возможном переполнении (если ваш язык, например, С++). Сумма квадратов: сумма квадратов всех чисел от 1 до n минус квадраты всех чисел в массиве.

Итак, вы за O(n) двумя не вложенными циклами (один для суммы квадратов 1..n, другой для обработки всех чисел массива) нашли X+Y=A и X^2 + Y^2=B.

Теперь решите уравнения относительно X и Y: Выразите X через Y из первого уравнения и подставьте во второе. Решите квадратное уравнение и получите:
X = (A-sqrt(2B-A^2))/2, Y = (A+sqrt(2B-A^2))/2.

Тут, хоть и есть квадратные корни, они в итоге дают целые числа.

Вариант тупой - для каждого элемента первого массива пройтись циклом по второму массиву и сравнить.

Вариант по-умнее: Отсортировать оба массива, пройтись по ним двумя указателями параллельно (Если текущие элементы совпали - нашли совпадение и двигаем оба указателья, иначе двигаем указатиль на меньший элемент. Если один из массивов кончился - все).

Лучший вариант: Пройтись по меньшему массиву и сложить его элементы в HashSet<> (через Add()). Потом пройтись по второму массиву и каждый элемент проверить через метод Contains() у сета.

После сведения к теории графов есть решение за O(n^3) через венгерский алгоритм (реализация) или через алгоритм посика максимального потока минимальной стоимости (Там реализация, медленнее венгерского метода. Вот решение за n^3, но код готовый я не нашел).



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

Невозможно решить вашу задачу. У вас 65535*255 вариантов входных данных и по условию они должны выдавать разные значения. Итоговое количество чуть не дотягивает до 2^24 - а значит в 16 бит его никак не засунуть.

Довольно частая ошибка. Лечится или переворачиванием логики, как вы заметили - проходиться по списку ids и смотреть, если такой в data.

Еще лучший вариант - вместо списка использовать какой-либо set в ids. Это будет работать совсем быстро, если ids длинный, а data короткий.

ООП. Объект - рамка. Должен содержать в себе список всех дочерних рамок (но не внуков - только тех, которые прямо в верхней содержатся, но не в чем другом).

При рисовании новой рамки рекурсивно спускайтесь по этому дереву объектов, пока не получите тот элемент, в котором новая рамка целиком содержится.

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

Если видите, что все дети текущего объекта не пересекаются с рамкой, то вы нашли рамку - родителя вашего нового объекта. Добавьте новую рамку к детям этого объекта. Теперь пройдитесь по всем детям и, если они целиком внутри новой рамки - перенесите их в детей этого нового объекта.

Как делать прорисовку? Опять же рекурсивный проход по дереву отсекает все элементы, которые не пересекаются с видимой областью. Те, которые пересекаются - сохраняются в какой-то список на прорисовку.

Это если рамок не слишком много, скажем до 1000. В противном случае придется повозиться и городить всякие BSP-tree, kd-tree для быстрого поиска объектов, но вам это, похоже не надо. Это будет слишком сложно.