evgeniy8705
@evgeniy8705
Повелитель вселенной

Как решить задачу про разрез(написать программу)?

Задача. Есть торт(квадратный). В него вставляют произвольное количество свечей. Необходимо проверить, можно ли разрезать его на две равные части, так чтобы в одной части не было свечей.(резать нужно не задев свечи).
Картинка - fastpic.ru/view/67/2015/0129/6f17589820129c216cd53...
.

Необязательно готовая программа(можно и в текстовом виде). Хотя бы подскажите алгоритм решения.
  • Вопрос задан
  • 4333 просмотра
Решения вопроса 1
Пригласить эксперта
Ответы на вопрос 4
Mrrl
@Mrrl
Заводчик кардиганов
Сначала проверяете, есть ли свеча в центре. Если есть, то очевидно, нельзя (любой разрез, делящий торт пополам, проходит через центр).
Потом для каждой свечи находите направление на неё из центра. В большинстве языков это делается вызовом функции atan2(y,x) (в предположении, что центр находится в точке (0,0)). Она выдаёт угол в радианах, лежащий в промежутке от -pi до pi.
Сортируете углы по возрастанию: a1<=a2<=...<=an.
Если an-a1 < pi-eps, то все свечи лежат внутри угла, меньшего pi, и разрез есть.
Если для какого-то k a{k+1}-ak > pi+eps, то есть пустой угол, больший pi, и разрез тоже есть.

Сложности возникают, когда an-a1 или a{k+1}-ak очень близки к pi, и надо точно проверить, больше угол, чем pi, меньше, или равен. Здесь всё зависит от жестокости авторов задачи.
Если числа заданы, как целые, не превосходящие по модулю 10^9, то достаточно посчитать определитель x{k+1}*y{k}-x{k}*y{k+1}, и по его знаку определить, с какой стороны линия, соединяющая свечи, пройдёт от центра. Произведения укладываются в int64, и всё просто.
Если числа целые и не превосходят 10^18, то дело хуже. Существуют алгоритмы проверки, не выходящие за int64 (специально написанный алгоритм Евклида), но возможно, что проще воспользоваться длинной арифметикой.
Хуже всего, если координаты - вещественные числа произвольного формата. Боюсь, что тут придётся писать свой парсер - простого хорошего способа надёжно проверить, что свечи с координатами, скажем (1.2E220, 2.7E-180) и (-2.8E200, 6.3E-200) лежат строго на одной прямой, проходящей через центр, я не знаю.
Ответ написан
Комментировать
@SilentFl
Я стал бы решать так: раз необходимо разрезать на две равные части, то линия разрезания обязательно проходит через центр торта. Теперь будем думать под каким углом (наклоном) разрезать - можно просто сделать перебор всех 180 градусов, но есть контраргумент в виде теста с существующим разрезанием, на котором все свечки расположены, допустим, за линией с наклонением в 0,9 градуса (перебор с десятыми долями градуса имеет точно такой же агрумент в 0,09 градуса). Вторая мысль - у нас же всего определенное количество свечей, давайте перебирать угол наклона по свечкам: берем свечу, делаем разрез, проходящий слева от нее и через центр торта и смотрим наличие слева и ниже от разреза свечек (подзадача взаимного расположения линии и точек на плоскости).
По оценке времени получается в лоб решать O(N^2), где N - количество свечек. Вполне вероятно что оценку можно улучшить до O(NlogN), применив какую-то структуру для поиска точек ниже-левее.
Ответ написан
Комментировать
gbg
@gbg Куратор тега Программирование
Любые ответы на любые вопросы
Вам нужно научиться определять, с какой стороны от прямой AB лежит точка Т.

vecmul.svg?dl=0

Если Q>0, значит условно - "слева", если меньше нуля "условно" - справа.
Ответ написан
nowfine
@nowfine
сисадмин 30+ левел
резать нужно в плоскости горизонта отставив лезвие примерно на половину высоты торта от его верхней плоскости
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы