Время

13:57:54
24 May 2012
Версия для печати

Точка и многоугольник

Как программисты меняют лампочку?
Они этого не делают, так как это аппаратная проблема!

   Я сейчас очень занят и немогу написать легенду для этой задачи. Так что скажем просто, что есть задача: для заданных выпуклого многоугольника и точки нужно определить, принадлежит ли точка многоугольнику или нет.


Технические условия

   Входные данные

   Входные данные содержат несколько тестовых случаев. Каждый тестовый случай содержит сначала целое число N (N1000), далее следует N пар целых чисел, содержащих координаты вершин многоугольника (X, Y) в порядке обхода против часовой стрелки. Следующая строка содержит два целых числа - координаты заданной точки. Входные данные заканчиваются строкой, содержащей единственное число 0. Все координаты лежат в интервале -1000X, Y1000.

   Выходные данные

   Для каждого тестового случая выведите в отдельной строке "INSIDE", если точка находится внутри многоугольника, "ON BORDER", если точка расположена на его стороне или "OUTSIDE", если точка не принадлежит многоугольнику.


Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 10
Сложность: 24% 16/21

Пример

Пример входных данных

4
4 0
4 4
0 4
0 0
2 2
3
0 0
2 0
1 1
-2 -2
0

Пример выходных данных

INSIDE
OUTSIDE


← Хазхир - король джунглей СБУ! Список задач Три K →