Определите, лежит ли набор линий на одной стороне точки, а другой набор линий лежит на другой стороне

Question

Учитывая два набора A и B линий с n строками и точкой p. Как определить, лежат ли линии A на одной стороне p, а линии B - на другой?

Answer 1

Предполагая следующее:
1. Это не домашняя работа.
2. «Крест P» означает, что для данного диапазона x, y они не пересекаются. Если мы говорим обо всей оси, то линии в A и B должны быть параллельны их множеству, и этот вопрос становится тривиальным.

Тогда простой (хотя и наивный) подход (O (n)) состоит в том, чтобы просто сравнивать каждое значение x в строках со значением x в точке (для заданного вами значения y для p). Если для заданного y все x-координаты множества A (или B) находятся слева от заданной точки, а для заданного x все значения y НЕ выше этой точки, то этот набор находится на одной стороне , Запустите тот же тест для другого набора, и если все линии находятся на другой стороне. Эт альт. :)

Надеюсь, это поможет.

Answer 2

Если все линии не параллельны друг другу, они всегда пересекают обе стороны p, поскольку они продолжаются вечно.В противном случае нарисуйте линию, параллельную одной из других линий, которая проходит через p, и эта линия разделит два набора.