Ш
Для каждого подмножества проверять отделяется ли оно от всего остального?
Да вот если для каждого подмножество узнать какая прямая их отделяет, То не понятно как склеить ответ
Size: a a a
2020 July 24
Ш
и чуток не понятно как проводить эту прямую
KK
Кто то знает как решить ?
Битмасками проверить можно ли провести линию между двумя множеством из единиц и нулей, а потом аккуратненько смерджить
KK
По дереву битмасок
Ш
ведь она не должна пересекать не одну точку из данных
EZ
Да вот если для каждого подмножество узнать какая прямая их отделяет, То не понятно как склеить ответ
Не тогда проверяй для пар подмножеств
CD
Битмасками проверить можно ли провести линию между двумя множеством из единиц и нулей, а потом аккуратненько смерджить
Перцептроном? :)
KK
Именно!
EZ
KK
*между первой и второй битмаской
KK
Ограничения же позволяют
EZ
Реализовывать это я конечно не буду
KK
Реализовывать это я конечно не буду
Да ладно, что такого
KK
Берем, центры масс
KK
У точек
KK
Между ними прямую
KK
И проецируем на нее все точки обоих множеств
KK
А, или нет, так не работает
KK
В общем, короче, делаем выпуклую оболочку одного из множеств и проверяем что ни одна из точек второго не лежит в нем
KK