「JOISC 2013 Day1」JOI 海报 题解

给定 $N$ 个点的坐标 $(X_i, Y_i)$ 和一个 $W \times H$ 的矩形区域。我们需要选择 $4$ 个不同的点 $A, B, C, D$，满足：

1. 以 $A$ 为圆心，$B$ 在圆上的圆 $O_1$ 完全包含 以 $C$ 为圆心，$D$ 在圆上的圆 $O_2$
2. 两个圆都完全位于矩形区域内

求满足条件的 $(A,B,C,D)$ 四元组的数量。

问题分析

关键约束

设：

• $R_1 = \text{dist}(A,B)$（$A$ 到 $B$ 的距离）
• $R_2 = \text{dist}(C,D)$（$C$ 到 $D$ 的距离）

条件1（包含关系）：圆 $O_1$ 完全包含圆 $O_2$

• 需要满足：$\text{dist}(A,C) + R_2 < R_1$
• 注意：是严格小于，因为圆 $O_2$ 上的点必须在圆 $O_1$ 的内部

条件2（边界约束）：圆在矩形内

• 对于以 $P$ 为圆心，半径 $R$ 的圆：
  • $R \leq \min(P_x, W-P_x, P_y, H-P_y)$
  • 即圆心到四条边界的距离都 $\geq R$

解决方案

暴力枚举（$O(N^4)$）

由于 $N \leq 50$，$C_{50}^4 \approx 230,300$，暴力枚举是可行的。

def solve_bruteforce(N, W, H, points):
    count = 0
    for i in range(N):          # A
        Ax, Ay = points[i]
        for j in range(N):      # B
            if j == i: continue
            Bx, By = points[j]
            R1 = dist(Ax, Ay, Bx, By)
            # 检查圆O1是否在矩形内
            if not circle_in_rect(Ax, Ay, R1, W, H):
                continue
                
            for k in range(N):  # C
                if k == i or k == j: continue
                Cx, Cy = points[k]
                for l in range(N):  # D
                    if l == i or l == j or l == k: continue
                    Dx, Dy = points[l]
                    R2 = dist(Cx, Cy, Dx, Dy)
                    # 检查圆O2是否在矩形内
                    if not circle_in_rect(Cx, Cy, R2, W, H):
                        continue
                    
                    # 检查包含关系
                    d_AC = dist(Ax, Ay, Cx, Cy)
                    if d_AC + R2 < R1:  # 严格小于
                        count += 1
    return count

优化思路

虽然 $O(N^4)$ 已经足够，但可以进行一些优化：

1. 预处理距离矩阵

# 预处理所有点对距离
dist_matrix = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i+1, N):
        d = math.hypot(points[i][0]-points[j][0], points[i][1]-points[j][1])
        dist_matrix[i][j] = dist_matrix[j][i] = d

2. 预检查圆的边界条件

对于每个点对 $(P, Q)$，先检查以 $P$ 为圆心、$Q$ 在圆上的圆是否在矩形内。

3. 分组优化

由于 $A$ 和 $B$ 是外圆的圆心和圆周点，我们可以先枚举所有合法的 $(A,B)$ 对，再枚举 $(C,D)$ 对。

详细算法步骤

1. 读入N, W, H和所有点的坐标
2. 预处理所有点对的距离（节省重复计算）
3. 初始化计数器 count = 0
4. 枚举所有可能的四元组 (A,B,C,D):
   a. 计算 R1 = dist(A,B)
   b. 检查圆(A,R1)是否完全在矩形内：
      - min(Ax, W-Ax, Ay, H-Ay) >= R1
   c. 计算 R2 = dist(C,D)
   d. 检查圆(C,R2)是否完全在矩形内：
      - min(Cx, W-Cx, Cy, H-Cy) >= R2
   e. 检查包含关系：
      - dist(A,C) + R2 < R1
5. 输出 count

实现细节

浮点数精度处理

由于使用距离计算，需要注意浮点数精度：

# 使用平方比较避免浮点数误差
def check_contain(A, R1, C, R2):
    # dist(A,C) + R2 < R1
    # 转换为平方比较
    d_sq = (A[0]-C[0])**2 + (A[1]-C[1])**2
    if d_sq == 0:
        return R2 < R1  # 同心圆的情况
    
    # 注意：这里不能直接平方，因为不等式不保持
    # 所以还是用浮点数计算，但可以加一个小的epsilon
    d = math.sqrt(d_sq)
    return d + R2 < R1 - 1e-9

边界检查优化

def circle_in_rect(cx, cy, r, W, H):
    return (r <= cx <= W - r) and (r <= cy <= H - r)

子任务分析

子任务1（80分）：圆不接触

当两个圆不接触时，条件 $\text{dist}(A,C) + R_2 < R_1$ 更容易满足，但算法实现相同。

子任务2（20分）：无附加限制

需要考虑圆可能相切的情况，但题目要求严格包含，所以相切也不满足条件。

复杂度分析

• 枚举四元组：$O(N^4)$
• 对于 $N=50$：$50^4 = 6,250,000$ 种组合
• 每种组合进行常数次操作
• 总操作数约几百万次，完全可行

完整代码示例

import math

def solve():
    N, W, H = map(int, input().split())
    points = [tuple(map(int, input().split())) for _ in range(N)]
    
    count = 0
    
    for i in range(N):
        Ax, Ay = points[i]
        for j in range(N):
            if i == j: continue
            Bx, By = points[j]
            R1 = math.hypot(Ax-Bx, Ay-By)
            
            # 检查圆O1边界
            if not (R1 <= Ax <= W-R1 and R1 <= Ay <= H-R1):
                continue
            
            for k in range(N):
                if k == i or k == j: continue
                Cx, Cy = points[k]
                for l in range(N):
                    if l == i or l == j or l == k: continue
                    Dx, Dy = points[l]
                    R2 = math.hypot(Cx-Dx, Cy-Dy)
                    
                    # 检查圆O2边界
                    if not (R2 <= Cx <= W-R2 and R2 <= Cy <= H-R2):
                        continue
                    
                    # 检查包含关系
                    d_AC = math.hypot(Ax-Cx, Ay-Cy)
                    if d_AC + R2 < R1 - 1e-9:  # 严格小于
                        count += 1
    
    print(count)

if __name__ == "__main__":
    solve()

算法标签

• 计算几何：圆心、半径、距离、包含关系
• 枚举/暴力搜索：$O(N^4)$ 枚举所有组合
• 条件检查：几何约束条件判断

总结

本题是一道计算几何的枚举题，由于数据范围较小（$N \leq 50$），直接 $O(N^4)$ 暴力枚举即可。关键点在于正确理解题目中的几何约束条件，并注意浮点数精度处理。