Photos
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Zenyk is walking around a castle which has the shape of a convex \(n\)-gon.
Initially, Zenyk stands at the point (0, 0).
On the \(i\)-th step, he moves from the point \((x, y)\) where he is currently standing to the point with coordinates \(\left(x + X_{(i-1) \% m + 1}, y + Y_{(i-1) \% m + 1}\right)\). If at the end of the step Zenyk is standing at a point strictly inside the castle, he takes photos.
As soon as he goes outside the castle or steps on its boundary at any moment in time, he immediately goes home and will not take any new photos.
How many photos will Zenyk take?
Input
The first line contains two integers \(n\) and \(m\).
The next \(n\) lines contain pairs of numbers \(x_i\), \(y_i\) — the coordinates of the polygon vertices in counterclockwise order.
The next \(m\) lines contain pairs of numbers \(X_i\), \(Y_i\) — the description of the \(i\)-th step.
Output
In a single line, output an integer — the answer to the problem.
If Zenyk will take infinitely many photos, output
-1.
Constraints
\(3 \le n \le 10^5\),
\(1 \le m \le 10^5\),
\(|x_i|, |y_i|, |X_i|, |Y_i| \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 4 -2 -2 2 -2 2 2 -2 2 -1 -1 1 -1 1 1 -1 1 | 1 |
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|