Геометрия

Максимизируя КПД, продолжаю разбирать популярные задачи с низким процентом решаемости. На очереди задача на геометрию: Неудивительно, почему эту задачу решают с большим количеством ошибок. Здесь и не очень удобное представление входных данных, и тонкие моменты про границу участка, и координаты до 50000, которые при перемножении как раз приводят к переполнению типа int. Но количество дачников не очень большое, значит решать можно на Python. Начнём со считывания данных: Так как результат по каждому...

Продолжим разбирать региональный этап Всероссийской олимпиады школьников по информатике 2009 года второй задаче первого тура. Читаем условие: Если бы ограничения в задаче были поменьше можно было бы проверить все целочисленные точки прямоугольника на принадлежность кругу с помощью теоремы Пифагора (а именно, что расстояние от точки до центра круга не превышает радиуса круга). Однако можно заметить, что в каждом столбце кругу принадлежит непрерывная последовательность точек. И если найти верхнюю (u)...

Одна из задач на геометрию с регионального этапа Всероссийской олимпиады школьников 2009 года, в которой используется интересная идея и совсем немного комбинаторики. Точек довольно много, чтобы перебрать все тройки и проверить, составляют ли они равнобедренный треугольник. Такое решение на олимпиаде набирало 40 баллов из 100. Давайте для начала будем перебирать лишь одну вершину - противоположную основанию. Если теперь выделить множество вершин, равноудалённых от выбранной, то все их попарные комбинации будут образовывать основание равнобедренного треугольника...

Иногда бывают задачи, решение которых укладывается в "считал, вывел", давайте рассмотрим одну из таких. Задача на геометрию, и, по классике, необходимо проверить пересекаются ли фигуры (в данном случае окружности). Давайте нарисуем и посмотрим, что же получается: Итак, если есть точка пересечения двух окружностей, то мы можем построить треугольник, соединив её с центрами этих окружностей. И сторонами этого треугольника будут два радиуса окружностей и расстояние между центрами (L). Если точки пересечения нет, тогда такой треугольник построить нельзя...

Ещё одна задача на геометрию, чтобы освежить формулу площади треугольника перед вторым туром регионального этапа Всероссийской олимпиады школьников по информатике. Давайте рассуждать. Кажется логичным, что следует взять три самых больших фрагмента и сделать из них забор. Что же может помешать? В каком случае получается ответ -1? Ответ заключается в правиле треугольника, которое гласит, что в любом невырожденном треугольнике сумма двух сторон больше третьей стороны. То есть может случиться так, что из трёх самых больших фрагментов один будет настолько большой, что превысит сумму оставшихся двух...

Новогодние и рождественские праздники прошли, поэтому давайте разберём задачу про мытьё посуды с сайта acmp.ru. Переходя от легенды задачи на язык математики, нам надо найти такой x, чтобы функция суммарного расстояния до заданных точек на плоскости была минимальна, то есть Аналитически это решать не очень просто, потому что надо найти производную, приравнять её к нулю и решить сложное уравнение. Поэтому давайте решать численно. Для поиска минимума функции можно применить тернарный поиск: разбиваем...