题解：AT_joisc2013_joi_poster JOIポスター (JOI Poster)

PenroseHUGO · 2025-12-15 21:43:58 · 题解

一、题意简述

给定一个大小为 W \times H 的矩形海报，上面有 N 颗星星。
从中选择 四颗不同的星星 A,B,C,D，构造两个圆：

• 圆 O_1：以 A 为圆心，经过 B（半径 r_1=|AB|）
• 圆 O_2：以 C 为圆心，经过 D（半径 r_2=|CD|）

要求：

1. 圆 O_1 严格包含 圆 O_2（O_2 的任意点都在 O_1 内部，不含 O_1 的圆周）。
2. 两个圆均 不超出 矩形区域 0\le X\le W,\ 0\le Y\le H（圆内部或圆周上的点都满足）。

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

二、几何条件转化

1）严格包含条件

设：

• r_1 = |AB|
• r_2 = |CD|
• 两圆心距为 |AC|

则 O_1 严格包含 O_2 的充要条件是：

注意：必须是严格小于，不能写成 \le。

2）圆在矩形内

对任意圆心 (x,y)，半径 r，圆完全在矩形内等价于：

允许相切（等号成立时圆周在边界上）。

三、算法思路

由于 N\le 50，可以直接暴力枚举所有 有序 四元组 (A,B,C,D)，并保证四个点互不相同。

对每组：

1. 计算 r_1=|AB|，判断圆 O_1 是否在矩形内。
2. 计算 r_2=|CD|，判断圆 O_2 是否在矩形内。
3. 判断是否满足严格包含：|AC|+r_2<r_1。

满足则计数加一。

四、复杂度分析

枚举四个点：

每次判定为常数时间，能够通过。

五、参考实现（C++）

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
};

double dist(const Point &a, const Point &b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

bool circle_inside_rect(const Point &c, double r, double W, double H) {
    return (c.x - r >= 0.0 &&
            c.x + r <= W &&
            c.y - r >= 0.0 &&
            c.y + r <= H);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    double W, H;
    cin >> N >> W >> H;

    vector<Point> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i].x >> p[i].y;
    }

    long long ans = 0;

    for (int a = 0; a < N; a++) {
        for (int b = 0; b < N; b++) if (b != a) {
            double r1 = dist(p[a], p[b]);

            // 外圆必须在矩形内
            if (!circle_inside_rect(p[a], r1, W, H)) continue;

            for (int c = 0; c < N; c++) if (c != a && c != b) {
                for (int d = 0; d < N; d++) if (d != a && d != b && d != c) {
                    double r2 = dist(p[c], p[d]);

                    // 内圆必须在矩形内
                    if (!circle_inside_rect(p[c], r2, W, H)) continue;

                    double center_dist = dist(p[a], p[c]);

                    // 严格包含：必须是 <
                    if (center_dist + r2 < r1) {
                        ans++;
                    }
                }
            }
        }
    }

    cout << ans << "\n";
    return 0;
}