题目大意

我们有一个 X_p × Y_p 的窗户（左下角在原点 (0,0)，右上角在 (X_p, Y_p)），上面有 N 只苍蝇（坐标已知）。 有一个形状固定的苍蝇拍（一个 K 个顶点的多边形）。 我们可以将苍蝇拍平移到窗户内的任意整数坐标位置（即苍蝇拍的所有顶点坐标均为整数，且整个拍子不能超出窗户边界）。 问：有多少种放置位置，使得没有任何一只苍蝇位于苍蝇拍的多边形内部、边上或顶点上。

问题分析与思路

这个问题可以分解为以下几个步骤：

1. 枚举所有可能的放置位置： 苍蝇拍可以平移。假设我们以苍蝇拍的某一个点（例如，最小X和最小Y的点，或者第一个顶点）作为“参考点”，那么整个拍子的位置就由这个参考点的位置决定。 设苍蝇拍的顶点集为 P。我们首先计算这个多边形的“包围盒”（Bounding Box），即最小坐标 (min_x, min_y) 和最大坐标 (max_x, max_y)。 那么，参考点 (ref_x, ref_y) 的可移动范围是：

   • ref_x 可以从 0 移动到 X_p - (max_x - min_x)
   • ref_y 可以从 0 移动到 Y_p - (max_y - min_y) 这样能保证整个拍子都在窗户内。

   但是，题目只说了顶点是整数，且拍子不能超出窗户，并没有说拍子的顶点坐标必须非负。然而，由于窗户左下角是 (0,0)，且拍子不能超出，所以平移后的所有顶点坐标自然都在 [0, X_p] 和 [0, Y_p] 范围内。我们可以枚举参考点的所有可能整数位置。

2. 判断一个位置是否合法： 对于枚举的一个位置，我们将苍蝇拍平移过去，得到新的顶点坐标。 然后，对于每一只苍蝇，我们需要判断它是否在这个平移后的多边形内（包括边界）。 如果任何一只苍蝇在多边形内或边上，那么这个位置就是非法的。 如果所有苍蝇都在多边形外，那么这个位置是合法的，方案数加一。

3. 关键算法：判断点是否在多边形内： 这是一个经典的计算几何问题。常用的方法是射线法：

   • 从点出发向右作一条水平射线。
   • 统计该射线与多边形边的交点数量。
   • 如果交点数量为奇数，点在多边形内；如果为偶数，点在多边形外。
   • 特别注意边界情况：如果点在多边形的某条边上（包括顶点），也视为被伤害。在射线法中，需要特殊处理射线穿过顶点的情况（通常采用“下闭上升”规则，即只统计从下往上穿过射线的边，或者只统计从上往下穿过的边，避免重复计数）。

算法优化

直接枚举所有可能的平移位置可能会超时，因为 X_p 和 Y_p 最大为 500，所以位置总数最多约为 500 * 500 = 250,000。 对于每个位置，需要检查 N 只苍蝇（最多 500*500=250,000 只），每次检查需要 O(K) 的时间（K 最大 100,000）。 最坏情况下计算量是 250,000 * 250,000 * 100,000，这是不可接受的。

优化思路：

• 预处理多边形信息：将多边形的边存储好，并预处理出用于射线法判断所需的信息。

• 减少枚举量：我们不需要枚举整个窗户。注意到，如果苍蝇拍移动了 (dx, dy)，那么原来在 (x, y) 的苍蝇，在新坐标系下，相对于苍蝇拍的位置是 (x - dx, y - dy)。 换句话说，一只苍蝇 (x, y) 会“禁止”苍蝇拍参考点落在 (x - p_x, y - p_y) 的位置，其中 (p_x, p_y) 是苍蝇拍坐标系下的某个点？更准确地说：

  设苍蝇拍原始顶点为 (vx_i, vy_i)。平移 (dx, dy) 后顶点为 (vx_i + dx, vy_i + dy)。 苍蝇 (fx, fy) 受伤害的条件是：(fx, fy) 在平移后的多边形内。 这等价于：将苍蝇坐标 (fx, fy) 反向平移 (-dx, -dy) 后，落在原始多边形内。 即点 (fx - dx, fy - dy) 在原始多边形内。

  所以，我们可以预先对原始苍蝇拍进行一次“点在多边形内”的预处理，然后对于每个可能的平移量 (dx, dy)，我们检查所有苍蝇的反向平移点是否在原始多边形外。

  但这样依然需要枚举所有 (dx, dy)。

• 进一步优化： 我们可以标记所有“非法”的平移量。 具体步骤：

  1. 对于每一只苍蝇 (fx, fy)，找出所有会使它被拍到的平移量 (dx, dy)。 即：(fx - dx, fy - dy) 在原始多边形内。 设 (px, py) = (fx - dx, fy - dy)，则 dx = fx - px, dy = fy - py。 所以，如果原始多边形覆盖了某个点 (px, py)，那么平移量 (fx - px, fy - py) 就是非法的。
  2. 由于 dx, dy 必须是整数，且在一定范围内，我们可以用一个二维布尔数组 forbidden[X_p][Y_p] 来标记非法的平移量。
  3. 遍历原始多边形所覆盖的所有整数点 (px, py)（这可以通过多边形栅格化算法，如扫描线填充算法得到，但K很大时可能比较慢；或者遍历所有可能的整数点，用射线法判断是否在多边形内，但范围可能很大）。
  4. 对于每个在原始多边形内的整数点 (px, py)，对于每只苍蝇 (fx, fy)，计算 dx = fx - px, dy = fy - py。如果 (dx, dy) 在窗户平移量的合法范围内，就标记 forbidden[dx][dy] = true。
  5. 最后，统计所有未被标记的 (dx, dy) 的数量。

  这个方法的复杂度大致是 O( (多边形覆盖的整数点数) * N )。如果多边形很小，则很快；如果多边形很大，覆盖很多点，则可能很慢。

• 更实际的优化（对于本题数据范围）： 由于 X_p, Y_p <= 500，我们可以直接枚举平移量 (dx, dy)，但用更快的点在多边形内判断（O(K) 但常数小），并且希望数据中 N 不会总是最大。 对于70%的小数据 (X_p, Y_p <= 100)，直接枚举是可行的 (100*100*N*K)，如果N和K不太大就能过。 对于100%的数据，可能需要更巧妙的优化，比如注意到多边形很大时，可能覆盖大部分窗户，那么合法位置很少，我们可以先判断多边形是否覆盖了某只苍蝇的原始位置，从而快速排除一些情况。

参考代码框架（直接枚举法，适用于小数据）

def point_in_polygon(x, y, poly):
    # 射线法判断点(x,y)是否在poly内(包括边界)
    n = len(poly)
    inside = False
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1)%n]
        # 检查点是否在边上
        if min(y1, y2) <= y <= max(y1, y2) and min(x1, x2) <= x <= max(x1, x2):
            if (y - y1) * (x2 - x1) == (x - x1) * (y2 - y1):
                return True
        # 射线与边相交判断
        if ((y1 > y) != (y2 > y)) and (x < (x2 - x1) * (y - y1) / (y2 - y1) + x1):
            inside = not inside
    return inside

def main():
    X_p, Y_p, N = map(int, input().split())
    flies = [tuple(map(int, input().split())) for _ in range(N)]
    K = int(input())
    poly = [tuple(map(int, input().split())) for _ in range(K)]
    
    # 计算多边形的包围盒
    min_x = min(x for x, y in poly)
    max_x = max(x for x, y in poly)
    min_y = min(y for x, y in poly)
    max_y = max(y for x, y in poly)
    
    width = max_x - min_x
    height = max_y - min_y
    
    # 枚举平移量(dx, dy)
    count = 0
    for dx in range(0, X_p - width + 1):
        for dy in range(0, Y_p - height + 1):
            # 检查所有苍蝇
            valid = True
            for fx, fy in flies:
                # 将苍蝇坐标反向平移，判断是否在原始多边形内
                if point_in_polygon(fx - dx, fy - dy, poly):
                    valid = False
                    break
            if valid:
                count += 1
    print(count)

if __name__ == "__main__":
    main()

总结

本题核心是计算几何中的点在多边形内判断，结合枚举和优化。

• 关键算法：射线法判断点与多边形关系。
• 优化思路：将问题从“移动多边形检查点”转化为“移动点检查多边形”，从而避免对每个平移位置重新计算多边形，但最终实现时仍需权衡枚举量和判断速度。
• 注意事项：必须正确处理点在边上的情况，因为这也算伤害苍蝇。

在实际竞赛中，需要根据数据范围选择最合适的优化方法。对于本题的最大数据，可能需要非常高效的实现才能通过。