409015: GYM103415 G Slope

There are $$$n$$$ points $$$(x_i,y_i)$$$ in the plane, and all $$$x_i$$$'s are different.

You have to process $$$q$$$ queries. Each query determines a subset of the $$$n$$$ given points within the rectangle $$$[x_l, x_r] \times [y_l, y_r]$$$; and the subset consists of all point $$$i$$$ that satisfies $$$x_l\le x_i\le x_r$$$ and $$$y_l\le y_i\le y_r$$$. The answer to the query is the minimal value of $$$\lvert\frac{y_i-y_j}{x_i-x_j}\rvert$$$, where $$$i$$$ and $$$j$$$ are different points in the subset described above and $$$\lvert a \rvert$$$ is the absolute value of $$$a$$$. If the subset contains less than two points, please refer to the output section.

The first line contains two positive integers $$$n$$$ and $$$q$$$ ($$$1\le n\le 7 \times 10^3$$$ and $$$1\le q\le 7 \times 10^5$$$).

The $$$i$$$-th line of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(-10^9\le x_i, y_i\le 10^9)$$$.

In the next $$$q$$$ lines, each contains four integers $$$x_l$$$, $$$x_r$$$, $$$y_l$$$, and $$$y_r$$$ $$$(-10^9\le x_l\le x_r\le 10^9$$$ and $$$-10^9\le y_l\le y_r \le 10^9)$$$ that constitute a query.

The output consists of $$$q$$$ lines. The $$$i$$$-th line contains two non-negative coprime integers $$$a$$$ and $$$b$$$, which represent the answer $$$\frac{a}{b}$$$ to the $$$i$$$-th query. If $$$a=0$$$, you should print '0 1'. If the subset contains less than two points, you should print '1 0'.

5 5
16 12
11 14
15 6
1 14
2 16
1 2 13 17
10 17 12 14
1 17 11 19
15 16 6 12
11 15 1 19

2 1
2 5
0 1
6 1
2 1