Problem K
Zoning Houses
Given a registry of all houses in your state or province, you would like to know the minimum size of an axis-aligned square zone such that every house in a range of addresses lies in the zone or on its border. The zoning is a bit lenient and you can ignore any one house from the range to make the zone smaller.
The addresses are given as integers from $1..n$. Zoning requests are given as a consecutive range of houses. A valid zone is the smallest axis-aligned square that contains all of the points in the range, ignoring at most one.
Given the ($x,y$) locations of houses in your state or province, and a list of zoning requests, you must figure out for each request: What is the length of a side of the smallest axis-aligned square zone that contains all of the houses in the zoning request, possibly ignoring one house?
Input
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line containing two integers $n$ and $q$ ($1 \le n,q \le 10^5$), where $n$ is the number of houses, and $q$ is the number of zoning requests.
The next $n$ lines will each contain two integers, $x$ and $y$ ($-10^9 \le x,y \le 10^9$), which are the ($x$,$y$) coordinates of a house in your state or province. The address of this house corresponds with the order in the input. The first house has address $1$, the second house has address $2$, and so on. No two houses will be at the same location.
The next $q$ lines will contain two integers $a$ and $b$ ($1 \le a < b \le n$), which represents a zoning request for houses with addresses in the range $[a..b]$ inclusive.
Output
Output $q$ lines. On each line print the answer to one of the zoning requests, in order: the side length of the smallest axis-aligned square that contains all of the points of houses with those addresses, if at most one house can be ignored.
Sample Input 1 | Sample Output 1 |
---|---|
3 2 1 0 0 1 1000 1 1 3 2 3 |
1 0 |
Sample Input 2 | Sample Output 2 |
---|---|
4 2 0 0 1000 1000 300 300 1 1 1 3 2 4 |
300 299 |