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

[Wednesday95]

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

[Алексей++]

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

[Finch]

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

PS Вроде эта

[Finch]

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

[Алексей++]

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

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

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

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

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

[Джон]

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

[Finch]

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

[Алексей++]

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