Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Задача про "разрезание" прямоугольника одной прямой, соблюдая условие  (Прочитано 20571 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Wednesday95
Новенький

lv
Offline Offline

« : 11-12-2018 22:20 » 

Здравствуйте! Помогите, пожалуйста, с решением этой задачи:
На торте прямоугольной формы расположены n клубничек и n вишенок. Клубнички находятся в точках с координатами (a1, y1), (a2, y2), ..., (an, yn), а вишенки c координатами (b1, y1), (b2, y2), ..., (bn, yn) (будем считать, что точка с координатами (x,y) находится соответственно на расстоянии x и y сантиметров от выбранных перпендикулярных сторон торта). Размеры ягод брать в расчёт не нужно.
Написать алгоритм, который бы за время O(n log n) давал ответ, возможно ли разрезать этот прямоугольный торт одной прямой (прямая необязательно должна быть перпендикулярна какой-то из сторон торта), чтобы на одной половине торта находились только ягоды вишни, а на другой только ягоды клубники.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 12-12-2018 04:51 » 

можно попробовать так:
- берём две самые левые вишенки с разными координатами Y, через них проводим линию. (таких линий может быть две, эти варианты нужно будет перебрать. Если все координаты Y вишенок одинаковые, то линия одна)
- разворачивам весь торт так, чтобы проведённая линия стала вертикальной
- теперь нужно выяснить, что слева от линии только клубника, а справа - только вишни
- разрезать можно по этой линии, либо по любой параллельной линии слева от неё, которая не заходит за клубнику
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #2 : 12-12-2018 16:40 » 

Если можно провести такой разрез, чтобы разделить вишни от клубник на торте. То обязательно найдутся две точки (вишни), Если провести через них линию, все остальные вишни будут находится по одну сторону, а все клубники по другу.ю сторону от данной линии.
Отсюда можно и плясать. Т.е. перебрать все возможные линии (проходяшие через вишни) и проверить данное условие. Нужна будет формула, стоит ли точка слева или справа от линии. У нас на форуме Dale когдато такую формулу приводил.

PS Вроде эта
« Последнее редактирование: 12-12-2018 16:51 от Finch » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #3 : 13-12-2018 04:46 » 

Предложенный мной способ не будет работать. Жаль Хотя есть другая идея. Нужно обдумать.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 13-12-2018 08:17 » 

Finch, я тут подумал - мой способ это тоже только частное решение, потому что всё это нужно повторить с каждой вишенкой.

Более свежая идея: из вишенок создаётся полигон П1, из клубник - П2. Полигон - логическое ИЛИ из всех треугольников, которые могут образовать ягоды полигона (причём, можно прямо в таком виде - список треугольников - и хранить модель полигона, чтобы не вычислять полигон-результат)

тогда задача сводится к:
- если П1 пересекается с П2, то решения нет.

- иначе - найти линию L, которая проходит через одно из рёбер полигона П1 и не пересекает  П1 и П2.
- разворачиваем торт так, чтобы линия L стала вертикальной. Все точки П1 должны быть с одной стороны линии L (либо на ней), а все точки П2 - с другой стороны линии L (либо на ней). Если это не так, нужно рассматривать другую линию L (новая итерация поиска L, так как линий L может быть несколько)

- иначе - найти ближайшую к линии L точку T2 полигона П2. Расстояние от T2 до L - это ширина "коридора" линий, параллельных L, которые являются решением задачи

Записан

Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #5 : 14-12-2018 00:47 » 

Вить, Лёш, а вы обратили внимание что ординаты у соответствующих пар земляника/черешня одинаковые? Ага
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #6 : 14-12-2018 03:43 » 

Я обратил внимание только на то, что топикпастеру эта тема не нужна. С тех пор, как он ее открыл, он так и не появился на форуме. Решение задачи Лешей на мой взгляд правильное. Единственное что, в задаче не просят найти саму линию разделения.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 14-12-2018 04:16 » 

Джон, ну копипастнул чувак, когда задание с бумажки переписывал )) Мне сама задача понравилась, а то, что ТС не появляется - это уже неважно, процесс пошёл
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines