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

A1cZheng · 2025-11-08 14:20:40 · 题解

思路：

由于 n \le 50，数据范围非常小，所以这道题可以直接愉快地四层循环枚举四个点 A,B,C,D。

设：

发现:

• 要使小圆被大圆完全包含，则： AC + r_2 < r_1。

• 要使圆心到矩形边界的最小距离必须不小于半径，则：r \le \min(x,W-x,y,H-y)。

于是，思路就很明确了：

1. 枚举四个点 A,B,C,D；
2. 计算出半径 r_1、r_2；
3. 判断两个圆是否都在海报内；
4. 如果 \text{dis} (A,C) + r_2 < r_1，则计数。

注意： 注意浮点数计算要加上微小容差，以避免精度误差。

:::info[Code]

#include<bits/stdc++.h>
using namespace std ;
const double f=1e-9;//微小容差
struct node {
    double x,y;
};
vector<node> s;
int n;
double w,h;
double dis (node a,node b) {
    double dx=a.x-b.x,dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
bool check(node a,double r,double w,double h) {
    return (r<=a.x)&&(r<=a.y)&&(r<=w-a.x)&&(r<=h-a.y);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>w>>h;
    for (int i=0;i<n;i++) {
        double x,y;
        cin>>x>>y;
        s.push_back({x,y});
    }
    long long ans=0;
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            if (i==j) continue;
            double r1=dis(s[i],s[j]);
            if (!check(s[i],r1,w,h)) continue;
            for (int k=0;k<n;k++) {
                if (k==i||k==j) continue;
                for (int l=0;l<n;l++) {
                    if (l==i||l==j||l==k) continue;
                    double r2=dis(s[k],s[l]);
                    if (!check(s[k],r2,w,h)) continue;
                    double ACdis=dis(s[i],s[k]);
                    if (ACdis+r2+f<r1) ans++;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

:::