Показать сообщение отдельно
  #6  
Старый 22.05.2010, 17:49
Alexey Gusakov

 
Сообщений: n/a

Можно и побыстрее. Проверять влоб через векторные произведения долго - это O(mn), где m, n - размеры многоугольников.
Можно с помощью бинпоиска проверять лежит ли точка внутри выпуклого многоугольника за логарифм, поэтому задача решается за O(m log n). С помощью бинарного поиска надо находить наибольшее k, для которого точка лежит левее, вектора 1,k.