Здравствуйте, помогите с такой задачей пожалуйста.
Нам дан многоугольник и точка, нужно проверить принадлежит ли точка многоугольнику. Многоугольник может быть как выпуклый, так и не выпуклый. Буду рад любой помощи:) Спасибо!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:45:57
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
11:45:57
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 05:49:04 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
http://habrahabr.ru/post/161237/
Автокомментарий: текст был обновлен пользователем AllDogsAreBeautiful (предыдущая версия, новая версия, сравнить).
С точки проводим бесконечный луч в рандомном направлении, считаем количество ребер которые пересекают этот луч. Если количество четное то снаружи, иначе внутри. Сложность O(N).
Только это правильно только в предположении, что рандомно проведённый луч не пройдёт ни через какую вершину. Если пройдёт и если этим нельзя пренебрегать, то придётся морочиться с тем, что принадлежность краям двух разных отрезков иногда надо считать за 1 раз (например: проводим горизонтальный луч, один отрезок идёт вверх от этой точки, другой вниз от неё же), а иногда за 0 раз (например: проводим горизонтальный луч, оба отрезка идут вниз от этой точки).
Проведите несколько рандомных лучей)
Если луч прошёл через вершину текущего отрезка, то мы проверяем, что это строго верхняя вершина отрезка (если мы луч провели горизонтально), тогда засчитываем пересечение.
ссылка
Разбить многоугольник на треугольники и проверить принадлежность точки каждому из них. Принадлежность треугольнику можно проверить через сравнение площадей.
Если и делать предподсчёт, то можно за O(log(n)) на запрос отвечать.