시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Grete has a polygon consisting of $n$ vertices. All sides of the polygon are parallel to the coordinate axes, and each two adjacent sides of the polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches.
Grete has $m$ queries and in each query, a point $(u_i, v_i)$ strictly inside the polygon is given. Grete would like to know the length of the side of the maximal square inside the polygon whose lower left corner is $(u_i, v_i)$.
The input consists of several test cases terminated by end-of-file. For each test case:
The first line contains two integers $n$ and $m$, which are the number of vertices and the number of queries.
Each of the next $n$ lines contains two integers $x_i$ and $y_i$, the coordinates of vertices of the polygon in counterclockwise order.
Each of the next $m$ lines contains two integers $u_i$ and $v_i$, the coordinates of the lower left corner.
For each query, output an integer denoting the length of the maximal square inside the polygon.
4 3 0 0 4 0 4 4 0 4 1 1 2 2 3 3 12 12 3050 2000 2000 2000 2000 3635 -2000 3635 -2000 2000 -2590 2000 -2590 -2000 -2000 -2000 -2000 -3481 2000 -3481 2000 -2000 3050 -2000 1415 -2882 -1100 498 -827 -3331 -114 -542 -1887 3485 -1606 -1463 -768 880 -1261 1180 330 2648 -1017 -2886 -1213 -585 -2025 -1966
3 2 1 585 3100 2827 2542 150 3606 2755 2455 987 3017 3213 3966