There are $N$ lines. Each line has an index between ${1}$ and $N$. The slope of each line is negative, i.e. it goes from upper-left to lower-right.

There are ${Q}$ queries. Each of them is in the format L R x y, and you should output whether there is any line with index between ${L}}$ and ${R}$ and the point $(x,y)$ is under it. If there is, then the answer is YES, otherwise NO.

As you know, any line splits an infinite plane into two regions. The point $(x,y)$ is under the line if that point is at the same region with point $(-\infty,-\infty)$. If the point lies on the line it does not count.

Input Format 

The first line contains $N$, the number of lines. The following $N$ lines each contains two integers $m$ and $n$ that describes the line $mx+n=y$.  

The next line contains ${Q}$, the number of queries. Each subsequent line contains 4 integers $L,R,x,y$.  

Output Format 

For each query, output one line containing either YES or NO.  

Constraints 

$1\leq N\leq10^5$ (Number of lines) 

$1\leq Q\leq10^5$ (Number of queries) 

$-10^9\leq x\leq10^9$ 

$-10^9\leq y\leq10^9$ 

$-10^9\leq m<0$ 

$-10^9\leq n\leq10^9$ 

$1\leq L\leq R\leq N$  

Sample Input  

2
-1 3
-2 -4
3
1 2 0 0
1 1 0 0
2 2 0 0

Sample Output  

YES
YES
NO

Explanation 

The image shows the two lines of the sample input.

Time Limits: C/C++ 1 sec, Java/C# 2 sec, other languages follow standard TL given in Environment

Source: hackerrank | Difficulty: HARD
Tags: Geometry


Solutions:
from collections import namedtuple
from bisect import bisect
from sys import stderr
line = namedtuple('line', 'm,b,i')
node = namedtuple('node', 'lo, hi, mid, hull, left, right')
hull = namedtuple('hull', 'lines, sep')

def main():
	(nlines,) = readints()
	lines = [readints() for _ in range(nlines)]
	(nreqs,) = readints()
	reqs = [readints() for _ in range(nreqs)]
	assert all((len(line) == 2 for line in lines))
	assert all((len(req) == 4 for req in reqs))
	segtree = getsegtree(lines)
	for req in reqs:
		print('YES' if below(segtree, *req) else 'NO')

def readints():
	return [int(f) for f in input().split()]

def getsegtree(lines):
	lines = [line(m, b, i) for (i, (m, b)) in enumerate(lines)]
	return treenode(0, len(lines) - 1, lines)

def treenode(lo, hi, lines):
	if lo == hi:
		return node(lo, hi, lo, gethull(lines[lo:hi + 1]), None, None)
	mid = (lo + hi) // 2
	(left, right) = (treenode(lo, mid, lines), treenode(mid + 1, hi, lines))
	return node(lo, hi, mid, gethull(left.hull.lines + right.hull.lines), left, right)

def below(segtree, lo, hi, x, y):
	(lo, hi) = (lo - 1, hi - 1)
	while True:
		if hi <= segtree.mid:
			if segtree.left is None:
				return hullbelow(segtree.hull, x, y)
			segtree = segtree.left
		elif lo > segtree.mid:
			segtree = segtree.right
		else:
			break
	if lo == segtree.lo and hi == segtree.hi:
		return hullbelow(segtree.hull, x, y)
	ltree = segtree.left
	while True:
		if lo <= ltree.lo:
			if hullbelow(ltree.hull, x, y):
				return True
			else:
				break
		elif lo <= ltree.mid:
			if hullbelow(ltree.right.hull, x, y):
				return True
			ltree = ltree.left
		else:
			ltree = ltree.right
	rtree = segtree.right
	while True:
		if rtree.hi <= hi:
			return hullbelow(rtree.hull, x, y)
		elif rtree.mid < hi:
			if hullbelow(rtree.left.hull, x, y):
				return True
			rtree = rtree.right
		else:
			rtree = rtree.left
	return False

def below0(segtree, lo, hi, x, y):
	if lo <= segtree.lo and segtree.hi <= hi:
		return hullbelow(segtree.hull, x, y)
	if hi <= segtree.mid:
		return below0(segtree.left, lo, hi, x, y)
	if segtree.mid < lo:
		return below0(segtree.right, lo, hi, x, y)
	return below0(segtree.left, lo, hi, x, y) or below0(segtree.right, lo, hi, x, y)

def gethull(lines):
	lines.sort()
	sep = []
	uselines = [lines[0]]
	for line in lines[1:]:
		if line.m == uselines[-1].m:
			if sep:
				sep.pop()
				uselines.pop()
			else:
				uselines[0] = line
				continue
		while True:
			inter = -((line.b - uselines[-1].b) // (line.m - uselines[-1].m))
			if len(sep) == 0 or inter > sep[-1]:
				sep.append(inter)
				uselines.append(line)
				break
			sep.pop()
			uselines.pop()
	return hull(sep=sep, lines=uselines)

def hullbelow(hull, x, y):
	line = hull.lines[bisect(hull.sep, x)]
	return y < line.m * x + line.b
main()


from collections import namedtuple
from bisect import bisect
from sys import stderr
line = namedtuple('line', 'm,b,i')
node = namedtuple('node', 'lo, hi, mid, hull, left, right')
hull = namedtuple('hull', 'lines, sep')

def main():
	(nlines,) = readints()
	lines = [readints() for _ in range(nlines)]
	(nreqs,) = readints()
	reqs = [readints() for _ in range(nreqs)]
	assert all((len(line) == 2 for line in lines))
	assert all((len(req) == 4 for req in reqs))
	segtree = getsegtree(lines)
	for req in reqs:
		print('YES' if below(segtree, *req) else 'NO')

def readints():
	return [int(f) for f in input().split()]

def getsegtree(lines):
	lines = [line(m, b, i) for (i, (m, b)) in enumerate(lines)]
	return treenode(0, len(lines) - 1, lines)

def treenode(lo, hi, lines):
	if lo == hi:
		return node(lo, hi, lo, gethull(lines[lo:hi + 1]), None, None)
	mid = (lo + hi) // 2
	(left, right) = (treenode(lo, mid, lines), treenode(mid + 1, hi, lines))
	return node(lo, hi, mid, gethull(left.hull.lines + right.hull.lines), left, right)

def below(segtree, lo, hi, x, y):
	(lo, hi) = (lo - 1, hi - 1)
	while True:
		if hi <= segtree.mid:
			if segtree.left is None:
				return hullbelow(segtree.hull, x, y)
			segtree = segtree.left
		elif lo > segtree.mid:
			segtree = segtree.right
		else:
			break
	if lo == segtree.lo and hi == segtree.hi:
		return hullbelow(segtree.hull, x, y)
	ltree = segtree.left
	while True:
		if lo <= ltree.lo:
			if hullbelow(ltree.hull, x, y):
				return True
			else:
				break
		elif lo <= ltree.mid:
			if hullbelow(ltree.right.hull, x, y):
				return True
			ltree = ltree.left
		else:
			ltree = ltree.right
	rtree = segtree.right
	while True:
		if rtree.hi <= hi:
			return hullbelow(rtree.hull, x, y)
		elif rtree.mid < hi:
			if hullbelow(rtree.left.hull, x, y):
				return True
			rtree = rtree.right
		else:
			rtree = rtree.left
	return False

def below0(segtree, lo, hi, x, y):
	if lo <= segtree.lo and segtree.hi <= hi:
		return hullbelow(segtree.hull, x, y)
	if hi <= segtree.mid:
		return below0(segtree.left, lo, hi, x, y)
	if segtree.mid < lo:
		return below0(segtree.right, lo, hi, x, y)
	return below0(segtree.left, lo, hi, x, y) or below0(segtree.right, lo, hi, x, y)

def gethull(lines):
	lines.sort()
	sep = []
	uselines = [lines[0]]
	for line in lines[1:]:
		if line.m == uselines[-1].m:
			if sep:
				sep.pop()
				uselines.pop()
			else:
				uselines[0] = line
				continue
		while True:
			inter = -((line.b - uselines[-1].b) // (line.m - uselines[-1].m))
			if len(sep) == 0 or inter > sep[-1]:
				sep.append(inter)
				uselines.append(line)
				break
			sep.pop()
			uselines.pop()
	return hull(sep=sep, lines=uselines)

def hullbelow(hull, x, y):
	line = hull.lines[bisect(hull.sep, x)]
	return y < line.m * x + line.b
main()


from collections import namedtuple
from bisect import bisect
from sys import stderr
line = namedtuple('line', 'm,b,i')
node = namedtuple('node', 'lo, hi, mid, hull, left, right')
hull = namedtuple('hull', 'lines, sep')

def main():
	(nlines,) = readints()
	lines = [readints() for _ in range(nlines)]
	(nreqs,) = readints()
	reqs = [readints() for _ in range(nreqs)]
	assert all((len(line) == 2 for line in lines))
	assert all((len(req) == 4 for req in reqs))
	segtree = getsegtree(lines)
	for req in reqs:
		print('YES' if below(segtree, *req) else 'NO')

def readints():
	return [int(f) for f in input().split()]

def getsegtree(lines):
	lines = [line(m, b, i) for (i, (m, b)) in enumerate(lines)]
	return treenode(0, len(lines) - 1, lines)

def treenode(lo, hi, lines):
	if lo == hi:
		return node(lo, hi, lo, gethull(lines[lo:hi + 1]), None, None)
	mid = (lo + hi) // 2
	(left, right) = (treenode(lo, mid, lines), treenode(mid + 1, hi, lines))
	return node(lo, hi, mid, gethull(left.hull.lines + right.hull.lines), left, right)

def below(segtree, lo, hi, x, y):
	(lo, hi) = (lo - 1, hi - 1)
	while True:
		if hi <= segtree.mid:
			if segtree.left is None:
				return hullbelow(segtree.hull, x, y)
			segtree = segtree.left
		elif lo > segtree.mid:
			segtree = segtree.right
		else:
			break
	if lo == segtree.lo and hi == segtree.hi:
		return hullbelow(segtree.hull, x, y)
	ltree = segtree.left
	while True:
		if lo <= ltree.lo:
			if hullbelow(ltree.hull, x, y):
				return True
			else:
				break
		elif lo <= ltree.mid:
			if hullbelow(ltree.right.hull, x, y):
				return True
			ltree = ltree.left
		else:
			ltree = ltree.right
	rtree = segtree.right
	while True:
		if rtree.hi <= hi:
			return hullbelow(rtree.hull, x, y)
		elif rtree.mid < hi:
			if hullbelow(rtree.left.hull, x, y):
				return True
			rtree = rtree.right
		else:
			rtree = rtree.left
	return False

def below0(segtree, lo, hi, x, y):
	if lo <= segtree.lo and segtree.hi <= hi:
		return hullbelow(segtree.hull, x, y)
	if hi <= segtree.mid:
		return below0(segtree.left, lo, hi, x, y)
	if segtree.mid < lo:
		return below0(segtree.right, lo, hi, x, y)
	return below0(segtree.left, lo, hi, x, y) or below0(segtree.right, lo, hi, x, y)

def gethull(lines):
	lines.sort()
	sep = []
	uselines = [lines[0]]
	for line in lines[1:]:
		if line.m == uselines[-1].m:
			if sep:
				sep.pop()
				uselines.pop()
			else:
				uselines[0] = line
				continue
		while True:
			inter = -((line.b - uselines[-1].b) // (line.m - uselines[-1].m))
			if len(sep) == 0 or inter > sep[-1]:
				sep.append(inter)
				uselines.append(line)
				break
			sep.pop()
			uselines.pop()
	return hull(sep=sep, lines=uselines)

def hullbelow(hull, x, y):
	line = hull.lines[bisect(hull.sep, x)]
	return y < line.m * x + line.b
main()


from collections import namedtuple
from bisect import bisect
from sys import stderr
line = namedtuple('line', 'm,b,i')
node = namedtuple('node', 'lo, hi, mid, hull, left, right')
hull = namedtuple('hull', 'lines, sep')

def main():
	(nlines,) = readints()
	lines = [readints() for _ in range(nlines)]
	(nreqs,) = readints()
	reqs = [readints() for _ in range(nreqs)]
	assert all((len(line) == 2 for line in lines))
	assert all((len(req) == 4 for req in reqs))
	segtree = getsegtree(lines)
	for req in reqs:
		print('YES' if below(segtree, *req) else 'NO')

def readints():
	return [int(f) for f in input().split()]

def getsegtree(lines):
	lines = [line(m, b, i) for (i, (m, b)) in enumerate(lines)]
	return treenode(0, len(lines) - 1, lines)

def treenode(lo, hi, lines):
	if lo == hi:
		return node(lo, hi, lo, gethull(lines[lo:hi + 1]), None, None)
	mid = (lo + hi) // 2
	(left, right) = (treenode(lo, mid, lines), treenode(mid + 1, hi, lines))
	return node(lo, hi, mid, gethull(left.hull.lines + right.hull.lines), left, right)

def below(segtree, lo, hi, x, y):
	(lo, hi) = (lo - 1, hi - 1)
	while True:
		if hi <= segtree.mid:
			if segtree.left is None:
				return hullbelow(segtree.hull, x, y)
			segtree = segtree.left
		elif lo > segtree.mid:
			segtree = segtree.right
		else:
			break
	if lo == segtree.lo and hi == segtree.hi:
		return hullbelow(segtree.hull, x, y)
	ltree = segtree.left
	while True:
		if lo <= ltree.lo:
			if hullbelow(ltree.hull, x, y):
				return True
			else:
				break
		elif lo <= ltree.mid:
			if hullbelow(ltree.right.hull, x, y):
				return True
			ltree = ltree.left
		else:
			ltree = ltree.right
	rtree = segtree.right
	while True:
		if rtree.hi <= hi:
			return hullbelow(rtree.hull, x, y)
		elif rtree.mid < hi:
			if hullbelow(rtree.left.hull, x, y):
				return True
			rtree = rtree.right
		else:
			rtree = rtree.left
	return False

def below0(segtree, lo, hi, x, y):
	if lo <= segtree.lo and segtree.hi <= hi:
		return hullbelow(segtree.hull, x, y)
	if hi <= segtree.mid:
		return below0(segtree.left, lo, hi, x, y)
	if segtree.mid < lo:
		return below0(segtree.right, lo, hi, x, y)
	return below0(segtree.left, lo, hi, x, y) or below0(segtree.right, lo, hi, x, y)

def gethull(lines):
	lines.sort()
	sep = []
	uselines = [lines[0]]
	for line in lines[1:]:
		if line.m == uselines[-1].m:
			if sep:
				sep.pop()
				uselines.pop()
			else:
				uselines[0] = line
				continue
		while True:
			inter = -((line.b - uselines[-1].b) // (line.m - uselines[-1].m))
			if len(sep) == 0 or inter > sep[-1]:
				sep.append(inter)
				uselines.append(line)
				break
			sep.pop()
			uselines.pop()
	return hull(sep=sep, lines=uselines)

def hullbelow(hull, x, y):
	line = hull.lines[bisect(hull.sep, x)]
	return y < line.m * x + line.b
main()


from collections import namedtuple
from bisect import bisect
from sys import stderr
line = namedtuple('line', 'm,b,i')
node = namedtuple('node', 'lo, hi, mid, hull, left, right')
hull = namedtuple('hull', 'lines, sep')

def main():
	(nlines,) = readints()
	lines = [readints() for _ in range(nlines)]
	(nreqs,) = readints()
	reqs = [readints() for _ in range(nreqs)]
	assert all((len(line) == 2 for line in lines))
	assert all((len(req) == 4 for req in reqs))
	segtree = getsegtree(lines)
	for req in reqs:
		print('YES' if below(segtree, *req) else 'NO')

def readints():
	return [int(f) for f in input().split()]

def getsegtree(lines):
	lines = [line(m, b, i) for (i, (m, b)) in enumerate(lines)]
	return treenode(0, len(lines) - 1, lines)

def treenode(lo, hi, lines):
	if lo == hi:
		return node(lo, hi, lo, gethull(lines[lo:hi + 1]), None, None)
	mid = (lo + hi) // 2
	(left, right) = (treenode(lo, mid, lines), treenode(mid + 1, hi, lines))
	return node(lo, hi, mid, gethull(left.hull.lines + right.hull.lines), left, right)

def below(segtree, lo, hi, x, y):
	(lo, hi) = (lo - 1, hi - 1)
	while True:
		if hi <= segtree.mid:
			if segtree.left is None:
				return hullbelow(segtree.hull, x, y)
			segtree = segtree.left
		elif lo > segtree.mid:
			segtree = segtree.right
		else:
			break
	if lo == segtree.lo and hi == segtree.hi:
		return hullbelow(segtree.hull, x, y)
	ltree = segtree.left
	while True:
		if lo <= ltree.lo:
			if hullbelow(ltree.hull, x, y):
				return True
			else:
				break
		elif lo <= ltree.mid:
			if hullbelow(ltree.right.hull, x, y):
				return True
			ltree = ltree.left
		else:
			ltree = ltree.right
	rtree = segtree.right
	while True:
		if rtree.hi <= hi:
			return hullbelow(rtree.hull, x, y)
		elif rtree.mid < hi:
			if hullbelow(rtree.left.hull, x, y):
				return True
			rtree = rtree.right
		else:
			rtree = rtree.left
	return False

def below0(segtree, lo, hi, x, y):
	if lo <= segtree.lo and segtree.hi <= hi:
		return hullbelow(segtree.hull, x, y)
	if hi <= segtree.mid:
		return below0(segtree.left, lo, hi, x, y)
	if segtree.mid < lo:
		return below0(segtree.right, lo, hi, x, y)
	return below0(segtree.left, lo, hi, x, y) or below0(segtree.right, lo, hi, x, y)

def gethull(lines):
	lines.sort()
	sep = []
	uselines = [lines[0]]
	for line in lines[1:]:
		if line.m == uselines[-1].m:
			if sep:
				sep.pop()
				uselines.pop()
			else:
				uselines[0] = line
				continue
		while True:
			inter = -((line.b - uselines[-1].b) // (line.m - uselines[-1].m))
			if len(sep) == 0 or inter > sep[-1]:
				sep.append(inter)
				uselines.append(line)
				break
			sep.pop()
			uselines.pop()
	return hull(sep=sep, lines=uselines)

def hullbelow(hull, x, y):
	line = hull.lines[bisect(hull.sep, x)]
	return y < line.m * x + line.b
main()


from collections import namedtuple
from bisect import bisect
from sys import stderr
line = namedtuple('line', 'm,b,i')
node = namedtuple('node', 'lo, hi, mid, hull, left, right')
hull = namedtuple('hull', 'lines, sep')

def main():
	(nlines,) = readints()
	lines = [readints() for _ in range(nlines)]
	(nreqs,) = readints()
	reqs = [readints() for _ in range(nreqs)]
	assert all((len(line) == 2 for line in lines))
	assert all((len(req) == 4 for req in reqs))
	segtree = getsegtree(lines)
	for req in reqs:
		print('YES' if below(segtree, *req) else 'NO')

def readints():
	return [int(f) for f in input().split()]

def getsegtree(lines):
	lines = [line(m, b, i) for (i, (m, b)) in enumerate(lines)]
	return treenode(0, len(lines) - 1, lines)

def treenode(lo, hi, lines):
	if lo == hi:
		return node(lo, hi, lo, gethull(lines[lo:hi + 1]), None, None)
	mid = (lo + hi) // 2
	(left, right) = (treenode(lo, mid, lines), treenode(mid + 1, hi, lines))
	return node(lo, hi, mid, gethull(left.hull.lines + right.hull.lines), left, right)

def below(segtree, lo, hi, x, y):
	(lo, hi) = (lo - 1, hi - 1)
	while True:
		if hi <= segtree.mid:
			if segtree.left is None:
				return hullbelow(segtree.hull, x, y)
			segtree = segtree.left
		elif lo > segtree.mid:
			segtree = segtree.right
		else:
			break
	if lo == segtree.lo and hi == segtree.hi:
		return hullbelow(segtree.hull, x, y)
	ltree = segtree.left
	while True:
		if lo <= ltree.lo:
			if hullbelow(ltree.hull, x, y):
				return True
			else:
				break
		elif lo <= ltree.mid:
			if hullbelow(ltree.right.hull, x, y):
				return True
			ltree = ltree.left
		else:
			ltree = ltree.right
	rtree = segtree.right
	while True:
		if rtree.hi <= hi:
			return hullbelow(rtree.hull, x, y)
		elif rtree.mid < hi:
			if hullbelow(rtree.left.hull, x, y):
				return True
			rtree = rtree.right
		else:
			rtree = rtree.left
	return False

def below0(segtree, lo, hi, x, y):
	if lo <= segtree.lo and segtree.hi <= hi:
		return hullbelow(segtree.hull, x, y)
	if hi <= segtree.mid:
		return below0(segtree.left, lo, hi, x, y)
	if segtree.mid < lo:
		return below0(segtree.right, lo, hi, x, y)
	return below0(segtree.left, lo, hi, x, y) or below0(segtree.right, lo, hi, x, y)

def gethull(lines):
	lines.sort()
	sep = []
	uselines = [lines[0]]
	for line in lines[1:]:
		if line.m == uselines[-1].m:
			if sep:
				sep.pop()
				uselines.pop()
			else:
				uselines[0] = line
				continue
		while True:
			inter = -((line.b - uselines[-1].b) // (line.m - uselines[-1].m))
			if len(sep) == 0 or inter > sep[-1]:
				sep.append(inter)
				uselines.append(line)
				break
			sep.pop()
			uselines.pop()
	return hull(sep=sep, lines=uselines)

def hullbelow(hull, x, y):
	line = hull.lines[bisect(hull.sep, x)]
	return y < line.m * x + line.b
main()