Блог пользователя tamir

Лежит ли точка строго внутри многоугольника ?
Автор tamir, 11 лет назад, По-русски

UPD: Задача решена.

Привет всем! У меня не получается написать задачу про определение точки внутри многоугольника. Нужна ваша помощь по задаче. Вот мой код. Вот задача. Спасибо за внимание!

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
  1. Если соединить точку со всеми вершинами, то многоугольник разобьётся на N треугольников. Ищешь сумму площадей этих треугольников и всего многоугольника и сравниваешь их!
  2. Можно пустить луч в случайном направлении из точки и посчитать, сколько сторон он пересечёт. Если нечётное, то точка лежит внутри.

2 вариант работает для любого многоугольника.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я использовал бинпоиск в своем решении. Мне хочется понять, где я ошибся. А 1-ый вариант у меня получился)

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    вариант 1 работает и для невыпуклых многоугольников, только нужно считать знаковую площадь (векторное произведение в помощь). Порядок обхода либо по часовой, либо против часовой — ну проверим оба варианта сравнив абсолютные величины.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Не правда, знаковая площадь не поможет. Нужно считать угол.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Да, похоже вру. Знаковая площадь может использоваться для вычисления площади невыпуклого многоугольника, а не того о чем спросил автор.

        → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Разве гарантируется порядок обхода вершин в входных данных?
Для лучшего понимания можно попробовать тривиальный тест:
=======
4
0 0
0 2
2 2
2 0
1 1
=======
YES
=======

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Насчет этого в условии задачи ничего не написано. Но мое решение прошло, которое работает при наличии порядка обхода. А ваш тест у меня не работает:(

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Об этом Lord_F и говорит! — если что-то в условии не запрещено, значит [почти наверняка] это будет в одном из тестов:
      -не сказано, что числа только целые — жди вещественные,
      -не сказано, что скорость положительная — жди отрицательную,
      -не сказано, что между городами ровно одна дорога — жди несколько дорог,
      и т.д. Так что в каждой задаче ИЩИТЕ ПОДВОХ! :)

      → Ответить