8813번 - Proste separujące 다국어

Danych jest n parami różnych punktów oraz m prostych na płaszczyźnie. Prostą nazwiemy separującą, jeśli w obu utworzonych przez nią półpłaszczyznach znajduje się przynajmniej po jednym punkcie ( prosta ta jest częścią każdej z dwóch utworzonych przez siebie półpłaszczyzn ). Które z podanych prostych są separujące?

W pierwszej linii znajduje się jedna liczba naturalna Z ( Z = 1 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii znajduje się jedna liczba naturalna n ( 1 <= n <= 100 000 ), oznaczająca liczbę punktów. W drugim wierszu występuje n par liczb naturalnych x, y ( 1 <= x, y <= 10⁹ ), pooddzielanych pojedynczymi odstępami - współrzędne kolejnych punktów.

W kolejnej linii znajduje się jedna liczba naturalna m ( 1 <= m <= 100 000 ), oznaczająca liczbę prostych do rozpatrzenia. W kolejnych m liniach znajdują się opisy tych prostych. Każdy taki opis składa się z czterech liczb naturalnych x₁, y_1, x₂, y₂ ( 1 <= x₁, y_1, x₂, y₂ <= 10⁹ ). Są to współrzędne dwóch różnych punktów, przez które przechodzi dana prosta.

Dla każdej prostej podanej na wejściu należy wypisać w osobnej linii słowo "TAK", jeśli prosta ta jest separująca, lub słowo "NIE" w przeciwnym przypadku.