The problem can be broken down into two simpler problems:

1. For a given polygon, find all integer points contained in its interior or on the edge.
2. For each possible position of the polygon, determine whether a fly exists with its position being equal to an integer point in the polygon, after its translation.

The first part of the algorithm will be solved using ray casting. A point is located within a polygon if and only if an arbitrary ray from that point intersects with the polygon in an odd number of points. However, there are special cases, because the ray can touch a polygon's vertex, and can contain a polygon's side. For details, consult the following post.

At the same time, we will check all integer points having the same ~x~ coordinate. We can find the intersections of each polygon's side with a vertical line through that ~x~ coordinate, and use the sweep line algorithm to check, for each point on the line, if they are inside of the polygon. This way, the complexity of the first part of the algorithm will be ~\mathcal O(Xp \times (Yp + N \log N))~. But, we can perform the entire procedure in only one sweep, by maintaining a set of lengths, so we don't have to sort the intersections for each ~x~ coordinate. The complexity of this procedure is ~\mathcal O(Xp \times (Yp+N) + N \log N)~.

We will reduce the second part of the algorithm to a problem in one dimension. Let ~(X_1, Y_1), (X_2, Y_2), \dots, (X_k, Y_k)~ denote all integer points within a given polygon translated such that its smallest ~X~ and ~Y~ coordinates are ~0~. We can represent these points with a binary string ~S_1~, where we write ~1~ at position ~2(Yp+2) \times Xi + Yi~ for each of the ~k~ points inside of the polygon, and write ~0~ for the remaining positions in the string. Now, translating the polygon for ~(X, Y)~ corresponds to translating the string for ~2(Yp+2) \times X + Y~. We define the string ~S_2~ that represents the flies in the same way.

We are left with determining, for each possible polygon translation, whether the bitwise and of the translated string ~S_1~ and string ~S_2~ is equal to ~0~. We can do this by using a bitset in the complexity of ~\mathcal O((Xp \times Yp)^2)~, but with a very small constant. But, a faster solution exists: we will reverse the string ~S_2~, and observe strings ~S_1~ and ~S_2~ as polynomials in the standard notation. From their product, we can make out the required information. The details of this approach are left as an exercise to the reader. If we implement the multiplication of polynomials using FFT, this part of the algorithm is of the complexity ~\mathcal O((Xp \times Yp) \log(Xp \times Yp))~.

The total complexity of the algorithm is ~\mathcal O(Xp \times N + N \log N + (Xp \times Yp) \log(Xp \times Yp))~.