Closing Ceremony [Junior and Senior]
The IOI organizing committee is planning to build a stage in the middle of a desert!
The desert can be represented as a 2-dimensional coordinate plane. The stage is rectangular in shape, and has to satisfy the following requirements:
- the sides of the stage are parallel to the axes,
- there are "supporting structures" on a pair of opposite corners of the stage,
- the area of the stage is exactly $K$.
Unfortunately, due to miscommunication, the workers have already built supporting structures at $N$ locations, where structure $i$ is located at coordinate $(x_i, y_i)$, for integers $1 \le i \le N$. Note that supporting structures are points on the coordinate plane with negligible width and height.
Help the committee to find two indices $1 \le i < j \le N$, so that the $i$-th and $j$-th supporting structures become the corners for the stage, or report that there is no such pair of supporting structures possible.
If there are multiple pairs of $(i, j)$ that can be used, output the lexicographically smallest such pair.
Note that we call a pair of integers $(a,b)$ to be lexicographically smaller than another pair of integers $(c,d)$ if and only if one of the conditions below are satisfied:
- $a < c$, or
- $a=c$ and $b < d$.
Input
The first line consists of two positive integers $N$ and $K$, denoting the number of supporting structures built, and the required area of the stage respectively.
Next $N$ lines contain two positive integers $x_i$ and $y_i$ each, denoting the coordinates of the $i$-th ($1 \le i \le N$) supporting structure.
Output
If there exists a valid pair of supporting structures, then output two integers $i$ and $j$, denoting the indices of the supporting structures that you have picked. If there are multiple valid pairs of $(i,j)$, output the lexicographically smallest such pair.
If no such valid pair of supporting structures exist, output -1.
Constraints
For all test cases, $2 \le N \le 10^5$, $1 \le K \le 10^8$, $1 \le x_i, y_i \le 10^8$, $(x_i, y_i) \neq (x_j, y_j)$ for all $1 \le i < j \le N$.
Subtask 1 (3 points): $N=4$.
Subtask 2 (11 points): $N \le 1000$.
Subtask 3 (13 points): $x_i, y_i \le 3000$ for all $1 \le i \le N$, $K \le 10^4$.
Subtask 4 (15 points): $K \le 10^4$.
Subtask 5 (28 points): $x_i, y_i \le 10^6$ for all $1 \le i \le N$.
Subtask 6 (30 points): No additional constraints.
Sample Test Cases
| Input | Output | |
|---|---|---|
| 5 12 3 4 1 1 2 2 3 7 4 5 |
2 4 | |
(Point $1$ is labelled as $A$, point $2$ is labelled as $B$, ...) There are two valid pairs of supporting structures: $(2, 4)$ and $(2, 5)$. $(2, 4)$ is the lexicographically smallest pair. |
||
Scoring: Per Subtask
Authored by onbert
Appeared in Joint-School Pre-HKOI Mini Competition 1