104 lines
2.8 KiB
Python
104 lines
2.8 KiB
Python
n, q = map(int, input().split())
|
|
|
|
coords = []
|
|
for _ in range(n):
|
|
x, y = map(int, input().split())
|
|
coords.append((x, y))
|
|
|
|
zone = []
|
|
for _ in range(q):
|
|
a, b = map(int, input().split())
|
|
zone.append((a, b))
|
|
|
|
|
|
def f(a, b, lst):
|
|
if b - a <= 1:
|
|
return 0
|
|
|
|
# minimum of the first 3
|
|
aXmin = min(lst[a][0], lst[a+1][0])
|
|
aXmax = max(lst[a][0], lst[a+1][0])
|
|
aYmin = min(lst[a][1], lst[a+1][1])
|
|
aYmax = max(lst[a][1], lst[a+1][1])
|
|
aLen = max(abs(aXmax-aXmin), abs(aYmax-aYmin))
|
|
|
|
bXmin = min(lst[a + 2][0], lst[a + 1][0])
|
|
bXmax = max(lst[a + 2][0], lst[a + 1][0])
|
|
bYmin = min(lst[a + 2][1], lst[a + 1][1])
|
|
bYmax = max(lst[a + 2][1], lst[a + 1][1])
|
|
bLen = max(abs(bXmax - bXmin), abs(bYmax - bYmin))
|
|
|
|
cXmin = min(lst[a][0], lst[a + 2][0])
|
|
cXmax = max(lst[a][0], lst[a + 2][0])
|
|
cYmin = min(lst[a][1], lst[a + 2][1])
|
|
cYmax = max(lst[a][1], lst[a + 2][1])
|
|
cLen = max(abs(cXmax - cXmin), abs(cYmax - cYmin))
|
|
|
|
if(aLen < bLen):
|
|
if(aLen < cLen):
|
|
osXmin = aXmin
|
|
osXmax = aXmax
|
|
osYmin = aYmin
|
|
osYmax = aYmax
|
|
osLen = aLen
|
|
else:
|
|
osXmin = cXmin
|
|
osXmax = cXmax
|
|
osYmin = cYmin
|
|
osYmax = cYmax
|
|
osLen = cLen
|
|
else:
|
|
if (bLen < cLen):
|
|
osXmin = bXmin
|
|
osXmax = bXmax
|
|
osYmin = bYmin
|
|
osYmax = bYmax
|
|
osLen = bLen
|
|
else:
|
|
osXmin = cXmin
|
|
osXmax = cXmax
|
|
osYmin = cYmin
|
|
osYmax = cYmax
|
|
osLen = cLen
|
|
|
|
nsLen = osLen
|
|
allXmin = min(aXmin, lst[a+2][0])
|
|
allXmax = max(aXmax, lst[a+2][0])
|
|
allYmin = min(aYmin, lst[a+2][1])
|
|
allYmax = max(aYmax, lst[a+2][1])
|
|
allLen = max(abs(allXmax-allXmin), abs(allYmax-allYmin))
|
|
# print(f"nsLen={nsLen}, osLen={osLen}, allLen={allLen}")
|
|
|
|
for i in lst[a + 3:b + 1]:
|
|
osXmin = min(osXmin, i[0])
|
|
osXmax = max(osXmax, i[0])
|
|
osYmin = min(osYmin, i[1])
|
|
osYmax = max(osYmax, i[1])
|
|
osLen = max(abs(osXmax - osXmin), abs(osYmax - osYmin))
|
|
|
|
nsXmin = allXmin
|
|
nsXmax = allXmax
|
|
nsYmin = allYmin
|
|
nsYmax = allYmax
|
|
nsLen = allLen
|
|
# print(f"nsLen={nsLen}, osLen={osLen}, allLen={allLen}")
|
|
|
|
allXmin = min(allXmin, i[0])
|
|
allXmax = max(allXmax, i[0])
|
|
allYmin = min(allYmin, i[0])
|
|
allYmax = max(allYmax, i[0])
|
|
allLen = max(abs(allXmax - allXmin), abs(allYmax - allYmin))
|
|
|
|
# print(f"nsLen={nsLen}, osLen={osLen}, allLen={allLen}")
|
|
if (nsLen < osLen):
|
|
osXmin = nsXmin
|
|
osXmax = nsXmax
|
|
osYmin = nsYmin
|
|
osYmax = nsYmax
|
|
|
|
return nsLen
|
|
|
|
|
|
for a, b in zone:
|
|
print(f(a-1, b-1, coords))
|