D. Точка в треугольнике

1000 мс · 256 МБ · всё или ничего

Дан треугольник и точка. Определите: внутри, на границе или снаружи.

Формат ввода

В первой строке - число запросов $q$ ( $1 \le q \le 10^5$ ).

В следующих $q$ строках - по восемь целых чисел: три вершины треугольника и точка. Вершины не лежат на одной прямой; координаты по модулю не превосходят $10^4$ .

Формат вывода

Для каждого запроса выведите INSIDE, BORDER или OUTSIDE.

Примеры

ввод

4
0 0 4 0 0 4 1 1
0 0 4 0 0 4 2 2
0 0 4 0 0 4 5 0
0 0 4 0 0 4 -1 -1

вывод

INSIDE
BORDER
OUTSIDE
OUTSIDE

ввод

2
0 0 4 0 0 4 0 0
0 0 4 0 0 4 4 4

вывод

BORDER
OUTSIDE

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.