"Разрезать" прямоугольник одной прямой, соблюдая условие

[Wednesday95]

Здравствуйте! Помогите, пожалуйста, с решением этой задачи:
На торте прямоугольной формы расположены $n$ клубничек и $n$ вишенок. Клубнички находятся в точках с координатами $(a_1,y_1)$, $(a_2,y_2)$, ..., $(a_n,y_n)$, а вишенки c координатами $(b_1,y_1)$, $(b_2,y_2)$, ..., $(b_n,y_n)$ (будем считать, что точка с координатами $(x,y)$ находится соответственно на расстоянии $x$ и $y$ сантиметров от выбранных перпендикулярных сторон торта). Размеры ягод брать в расчёт не нужно.
В задании требуется написать алгоритм, который бы за время $O(n \log n)$ давал ответ, возможно ли разрезать этот прямоугольный торт одной прямой (прямая необязательно должна быть перпендикулярна какой-то из сторон торта), чтобы на одной половине торта находились только ягоды вишни, а на другой только ягоды клубники.

На данном этапе размышлений мне непонятно как вообще подступиться к заданию.
Данная задача: http://altim.narod.ru/Docs/Russian/Manu ... public.htm лишь подтолкнула на мысль, что система координат будет распологаться не в центре, а как на прикрепленном рисунке (где буквой "а" обозначены клубнички, а буквой "b" ягоды вишни).


Буду очень признательна, если наведёте на мысль, которая может помочь в решении!

[Lia]

Wednesday95 в сообщении #1360585 писал(а):

Написать алгоритм,

Это поручение?

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.