package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type Point struct {
x, y int
}
type Segment struct {
A, B Point
}
type AABB struct {
minX, minY, maxX, maxY float64
}
type BVHNode struct {
box AABB
left *BVHNode
right *BVHNode
seg int
}
var S []Segment
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func minF(a, b float64) float64 {
if a < b {
return a
}
return b
}
func maxF(a, b float64) float64 {
if a > b {
return a
}
return b
}
func boundingBox(A, B Point) AABB {
return AABB{
minX: float64(min(A.x, B.x)),
minY: float64(min(A.y, B.y)),
maxX: float64(max(A.x, B.x)),
maxY: float64(max(A.y, B.y)),
}
}
func unionAABB(a, b AABB) AABB {
return AABB{
minX: minF(a.minX, b.minX),
minY: minF(a.minY, b.minY),
maxX: maxF(a.maxX, b.maxX),
maxY: maxF(a.maxY, b.maxY),
}
}
func buildBVH(segs []int) *BVHNode {
if len(segs) == 1 {
return &BVHNode{
box: boundingBox(S[segs[0]].A, S[segs[0]].B),
seg: segs[0],
}
}
var minCx, maxCx, minCy, maxCy float64 = 1e10, -1e10, 1e10, -1e10
for _, i := range segs {
cx := float64(S[i].A.x+S[i].B.x) / 2
cy := float64(S[i].A.y+S[i].B.y) / 2
minCx = minF(minCx, cx)
maxCx = maxF(maxCx, cx)
minCy = minF(minCy, cy)
maxCy = maxF(maxCy, cy)
}
var leftSegs, rightSegs []int
if maxCx-minCx > maxCy-minCy {
mid := (minCx + maxCx) / 2
for _, i := range segs {
cx := float64(S[i].A.x+S[i].B.x) / 2
if cx <= mid {
leftSegs = append(leftSegs, i)
} else {
rightSegs = append(rightSegs, i)
}
}
} else {
mid := (minCy + maxCy) / 2
for _, i := range segs {
cy := float64(S[i].A.y+S[i].B.y) / 2
if cy <= mid {
leftSegs = append(leftSegs, i)
} else {
rightSegs = append(rightSegs, i)
}
}
}
if len(leftSegs) == 0 || len(rightSegs) == 0 {
leftSegs = segs[:len(segs)/2]
rightSegs = segs[len(segs)/2:]
}
left := buildBVH(leftSegs)
right := buildBVH(rightSegs)
return &BVHNode{
box: unionAABB(left.box, right.box),
left: left,
right: right,
seg: -1,
}
}
func ccw(A, B, C Point) int64 {
return int64(B.x-A.x)*int64(C.y-A.y) - int64(B.y-A.y)*int64(C.x-A.x)
}
func onSegment(A, B, C Point) bool {
return min(A.x, B.x) <= C.x && C.x <= max(A.x, B.x) &&
min(A.y, B.y) <= C.y && C.y <= max(A.y, B.y)
}
func openClosedIntersect(P, t, C, D Point) bool {
cp1 := ccw(P, t, C)
cp2 := ccw(P, t, D)
cp3 := ccw(C, D, P)
cp4 := ccw(C, D, t)
if ((cp1 > 0 && cp2 < 0) || (cp1 < 0 && cp2 > 0)) &&
((cp3 > 0 && cp4 < 0) || (cp3 < 0 && cp4 > 0)) {
return true
}
if cp1 == 0 && onSegment(P, t, C) && C != P && C != (Point{0, 0}) {
return true
}
if cp2 == 0 && onSegment(P, t, D) && D != P && D != (Point{0, 0}) {
return true
}
if cp3 == 0 && onSegment(C, D, P) && P != C && P != D {
return true
}
if cp4 == 0 && onSegment(C, D, Point{0, 0}) {
return true
}
return false
}
func segAABBIntersect(A, B Point, box AABB) bool {
minX := float64(min(A.x, B.x))
maxX := float64(max(A.x, B.x))
minY := float64(min(A.y, B.y))
maxY := float64(max(A.y, B.y))
if maxX < box.minX-0.1 || minX > box.maxX+0.1 {
return false
}
if maxY < box.minY-0.1 || minY > box.maxY+0.1 {
return false
}
return true
}
func isDirectClear(A, t Point, node *BVHNode) bool {
if !segAABBIntersect(A, t, node.box) {
return true
}
if node.seg != -1 {
return !openClosedIntersect(A, t, S[node.seg].A, S[node.seg].B)
}
return isDirectClear(A, t, node.left) && isDirectClear(A, t, node.right)
}
func rayAABBIntersect(A Point, d Point, box AABB) bool {
ox := float64(A.x)
oy := float64(A.y)
dx := float64(d.x)
dy := float64(d.y)
tmin := -1e10
tmax := 1e10
if dx != 0 {
tx1 := (box.minX - 0.1 - ox) / dx
tx2 := (box.maxX + 0.1 - ox) / dx
tmin = maxF(tmin, minF(tx1, tx2))
tmax = minF(tmax, maxF(tx1, tx2))
} else {
if ox < box.minX-0.1 || ox > box.maxX+0.1 {
return false
}
}
if dy != 0 {
ty1 := (box.minY - 0.1 - oy) / dy
ty2 := (box.maxY + 0.1 - oy) / dy
tmin = maxF(tmin, minF(ty1, ty2))
tmax = minF(tmax, maxF(ty1, ty2))
} else {
if oy < box.minY-0.1 || oy > box.maxY+0.1 {
return false
}
}
return tmax >= tmin && tmax >= 0
}
func raySegmentIntersect(A, d, C, D Point) (bool, int64, int64) {
B := Point{A.x + d.x, A.y + d.y}
cp1 := ccw(A, B, C)
cp2 := ccw(A, B, D)
if (cp1 > 0 && cp2 > 0) || (cp1 < 0 && cp2 < 0) || (cp1 == 0 && cp2 == 0) {
return false, 0, 0
}
num := ccw(C, D, A)
den := num - ccw(C, D, B)
if den == 0 {
return false, 0, 0
}
if den < 0 {
num = -num
den = -den
}
if num <= 0 {
return false, 0, 0
}
return true, num, den
}
func getFirstHit(A, d Point, ignoreSeg int, node *BVHNode) (int, int64, int64) {
if !rayAABBIntersect(A, d, node.box) {
return -1, 0, 0
}
if node.seg != -1 {
if node.seg == ignoreSeg {
return -1, 0, 0
}
ok, num, den := raySegmentIntersect(A, d, S[node.seg].A, S[node.seg].B)
if ok {
return node.seg, num, den
}
return -1, 0, 0
}
leftHit, lNum, lDen := getFirstHit(A, d, ignoreSeg, node.left)
rightHit, rNum, rDen := getFirstHit(A, d, ignoreSeg, node.right)
if leftHit != -1 && rightHit != -1 {
if lNum*rDen < rNum*lDen {
return leftHit, lNum, lDen
}
return rightHit, rNum, rDen
}
if leftHit != -1 {
return leftHit, lNum, lDen
}
return rightHit, rNum, rDen
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
buf := make([]byte, 1024*1024)
scanner.Buffer(buf, 1024*1024)
scanner.Split(bufio.ScanWords)
nextInt := func() int {
scanner.Scan()
v, _ := strconv.Atoi(scanner.Text())
return v
}
if !scanner.Scan() {
return
}
n, _ := strconv.Atoi(scanner.Text())
S = make([]Segment, n)
for i := 0; i < n; i++ {
S[i].A.x = nextInt()
S[i].A.y = nextInt()
S[i].B.x = nextInt()
S[i].B.y = nextInt()
}
q := nextInt()
queries := make([]Point, q)
for i := 0; i < q; i++ {
queries[i].x = nextInt()
queries[i].y = nextInt()
}
var root *BVHNode
if n > 0 {
segs := make([]int, n)
for i := 0; i < n; i++ {
segs[i] = i
}
root = buildBVH(segs)
}
var V []Point
var V_S0 []int
t := Point{0, 0}
for i := 0; i < n; i++ {
for _, P := range []Point{S[i].A, S[i].B} {
d := Point{-P.x, -P.y}
if d.x == 0 && d.y == 0 {
continue
}
v := Point{S[i].B.x - S[i].A.x, S[i].B.y - S[i].A.y}
dot := int64(d.x)*int64(v.x) + int64(d.y)*int64(v.y)
lenD2 := int64(d.x)*int64(d.x) + int64(d.y)*int64(d.y)
lenV2 := int64(v.x)*int64(v.x) + int64(v.y)*int64(v.y)
if 2*dot*dot <= lenD2*lenV2 {
continue
}
P_other := S[i].A
if P == S[i].A {
P_other = S[i].B
}
u := Point{P.x - P_other.x, P.y - P_other.y}
dot2 := int64(d.x)*int64(u.x) + int64(d.y)*int64(u.y)
if dot2 <= 0 {
continue
}
if isDirectClear(P, t, root) {
V = append(V, d)
V_S0 = append(V_S0, i)
}
}
}
reachesTForV := make([][]bool, len(V))
for vIdx, d := range V {
S0 := V_S0[vIdx]
nextSeg := make([]int, n)
for i := 0; i < n; i++ {
nextSeg[i] = -1
v := Point{S[i].B.x - S[i].A.x, S[i].B.y - S[i].A.y}
dot := int64(d.x)*int64(v.x) + int64(d.y)*int64(v.y)
lenD2 := int64(d.x)*int64(d.x) + int64(d.y)*int64(d.y)
lenV2 := int64(v.x)*int64(v.x) + int64(v.y)*int64(v.y)
if 2*dot*dot <= lenD2*lenV2 {
continue
}
var PFwd Point
if dot > 0 {
PFwd = S[i].B
} else if dot < 0 {
PFwd = S[i].A
} else {
continue
}
hitSeg, _, _ := getFirstHit(PFwd, d, i, root)
nextSeg[i] = hitSeg
}
prevSeg := make([][]int, n)
for i := 0; i < n; i++ {
if nextSeg[i] != -1 {
prevSeg[nextSeg[i]] = append(prevSeg[nextSeg[i]], i)
}
}
reaches := make([]bool, n)
var dfs func(int)
dfs = func(u int) {
reaches[u] = true
for _, nxt := range prevSeg[u] {
if !reaches[nxt] {
dfs(nxt)
}
}
}
dfs(S0)
reachesTForV[vIdx] = reaches
}
for _, qPt := range queries {
if isDirectClear(qPt, t, root) {
fmt.Println("YES")
continue
}
found := false
for vIdx, d := range V {
hitSeg, _, _ := getFirstHit(qPt, d, -1, root)
if hitSeg != -1 && reachesTForV[vIdx][hitSeg] {
found = true
break
}
}
if found {
fmt.Println("YES")
} else {
fmt.Println("NO")
}
}
}