题解：P14433 [JOISC 2013] JOI 海报 / JOI Poster

题目传送门

题意

有 $N$ 个点，选出四个不同的点 $A, B, C, D$：

• 以 $A$ 为圆心、$B$ 在圆上作圆 $O_1$
• 以 $C$ 为圆心、$D$ 在圆上作圆 $O_2$
• 圆 $O_1$ 完全包含圆 $O_2$（不接触）
• 两个圆都在海报内部

求满足条件的四元组数量。

思路

直接枚举所有 $A, B, C, D$ 的组合，检查：

1. 圆 $O_1$ 在海报内：半径 $r_1 \le$ 圆心 $A$ 到海报边界的最小距离
2. 圆 $O_2$ 在海报内：半径 $r_2 \le$ 圆心 $C$ 到海报边界的最小距离
3. 包含关系：$|AC| + r_2 < r_1$

代码

#include <bits/stdc++.h>
#define Jason227 return
#define Code 0
using namespace std;

int n, w, h, ans = 0;
double r1, m1, r2, m2;

struct Point{
    int x, y;
};

double dis(Point a, Point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main(){
    cin >> n >> w >> h;
    vector<Point> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i].x >> p[i].y;
    }
    for(int a = 0; a < n; a++){
        for(int b = 0; b < n; b++){
            if(a == b)
                continue;
            r1 = dis(p[a], p[b]);
            m1 = min(min(p[a].x, w - p[a].x), min(p[a].y, h - p[a].y));
            if(r1 > m1 + 1e-9)
                continue;
            for(int c = 0; c < n; c++){
                if(c == a || c == b)
                    continue;
                for(int d = 0; d < n; d++){
                    if(d == a || d == b || d == c)
                        continue;
                    r2 = dis(p[c], p[d]);
                    m2 = min(min(p[c].x, w - p[c].x), min(p[c].y, h - p[c].y));
                    if(r2 > m2 + 1e-9)
                        continue;
                    if(dis(p[a], p[c]) + r2 < r1 - 1e-9){
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    Jason227 Code;
}

复杂度分析

• 时间复杂度：$O(N^4)$，通过四重循环枚举所有可能的四元组
• 空间复杂度：$O(N)$，用于存储点的坐标

AC 记录