Задача №3881. Пересечение
Компания, производящая оборудование для сотовой связи, обратилась к вам с просьбой написать программу, оценивающую качество организации сети. Одним из важных параметров является то, пересекаются ли зоны покрытия передатчиков, работающих на одинаковых частотах. Для простоты будем считать, что область покрытия каждого передатчика представляет собой многоугольник на плоскости (не обязательно выпуклый). Две области покрытия будем считать пересекающимися, если у них есть хотя бы одна общая точка (возможно, лежащая на границе одной или даже обеих областей). Ваша программа должна принимать на вход набор пар многоугольников, описывающих зоны покрытия передатчиков, и выводить про каждую пару информацию о том, пересекаются ли эти зоны.
На первой строке входного файла находится число \(K\) — количество тестов во входном файле. Далее идёт описание \(K\) тестов. Каждый тест задаётся описанием двух многоугольников, которые надо проверить на пересечение. Каждый многоугольник задаётся в следующем формате: сначала указывается одно число \(N_i\) — число вершин этого многоугольника, после чего идут \(N_i\) строк, каждая из которых содержит два разделённых пробелом числа \(x_{ij}\) и \(y_{ij}\) — координаты \(j\)-й вершины этого многоугольника. Вершины перечислены в порядке обхода многоугольника.
Число пар многоугольников в одном тесте \(1 \leq K \leq 10\), число вершин каждого многоугольника \(3 \leq N_i \leq 100\), координаты вершин — целые числа, \(|x_{ij}|, |y_{ij}| \leq 10\,000\).
Для каждой пары многоугольников выведите в выходной файл на отдельной строке одно слово: “YES”, если многоугольники пересекаются, и “NO”, если нет.
2 3 0 0 -1 0 0 -1 3 1 1 2 1 1 2 4 0 0 2 0 2 2 0 2 4 1 1 3 1 3 3 1 3
NO YES