Лабораторный практикум по информатике
Задача 4. «Тигр в загоне»
жүктеу/скачать 1,1 Mb.
|
| Задача 4. «Тигр в загоне». Недалеко от города Х находится запо- ведник, в котором обитают уссурийские тигры. Работники заповедни- ка очень переживают, когда тигр покидает охраняемую зону. Про- грамма охраны уссурийских тигров предусматривает снабжение каждого тигра ошейником с радиомаяком. Сигнал от тигриного ра- диомаяка поступает в центр охраны и позволяет определить местопо- ложение тигра. Территория заповедника представляет собой произ- вольный многоугольник.
Исходные данные: N – количество вершин многоугольника, задаю- щего заповедник, (xi, yi) – координаты его вершин, i = 1, 2, …, N. (X, Y) – координаты точки, в которой находится тигр. Требуется определить, находится ли тигр на территории заповед- ника, или надо срочно снаряжать спасательную экспедицию. Рис. 16.6. Иллюстрация к задаче «Тигр» Очень часто при решении задач геометрического содержания тре- буется проверить, лежит ли заданная точка внутри или вне многоуголь- ника. Таким способом можно решить, например, задачу о Бармаглоте, проверяя каждую точку Бармаглота относительно одеяла- многоугольника. Есть много способов проверки принадлежности точки многоугольнику, однако мы приведем здесь один из них, основанный на использовании произведения векторов. Идея метода заключается в том, чтобы определить сумму углов, под которыми стороны многоугольника видны из проверяемой точки. Если точка лежит внутри многоугольника, то суммарный угол равен 2π (точка Р на рисунке), если же точка лежит вне многоугольника, то сум- ма углов не равна 2π (точка Q). Таким образом, для решения надо перебрать в цикле последова- тельно все вершины многоугольника и найти сумму углов между векто- рами PAi и PAi+1, i = 1, 2, …, N. Не забудьте добавить угол между векто- рами PAN и PA1. Для определения величины угла между векторами нам потребуется формула скалярного произведения. Так как стороны многоугольника должны рассматриваться после- довательно, в порядке обхода вершин, то при нахождении суммарного угла следует учитывать взаимное расположение векторов. Угол, под ко- торым сторона видна из исследуемой точки, может быть как положи- тельным, так и отрицательным. Для определения знака угла воспользу- емся векторным произведением. Знак векторного произведения и определит знак конкретного угла в общей сумме. жүктеу/скачать 1,1 Mb. Достарыңызбен бөлісу:
|