Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » triangles
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Даны K точек с положительными целыми координатами. Также даны M треугольников, координаты одной из вершин которых лежат на координате 0, 0 (начала координат), координаты остальных двух вершин являются целыми положительными числами. Определите для каждого треугольника, находится ли хотя бы одна из K точек внутри нее (никакая точка не является вершиной треугольника).
1<=k,m<=10^5
1<=x,y<=10^9
посмотри псевдо скалярное произведение (или его еще называют косым произведение векторов), там где про направленные площади. с его помощью можно решить данную задачу. также есть еще один способ, разбить на 3 треугольника: т.е. дана точка и координаты треугольника, разбивай на три треугольника, если сумма площадей этих треугольников ровна площади данного треугольника, то точка принадлежит треугольнику, тут поможет формула Герона, но у этого метода недостаток в том что будут потери в точности, так что лучше косым произведение.
Смотри проблему Tri и ее решение http://www.ceoi2009.ro/view_page.php?id=24
А как за logN отвечать на запрос: лежит ли точка внутри многоугольника
Отсортировать все точки многоугольника по углу, далее дихотомией по углу..
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » triangles