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

Recall_cpp · 2025-11-06 19:30:51 · 题解

简单几何题。

由于 k 的个数很小，考虑暴力枚举每个点，判重。

然后求出两个圆的圆心，半径，设半径分别为 R,r，其中 R 为大圆半径。

判出界是容易的，直接让圆心向上、下、左、右都走半径步，看看是否在范围内。

然后设两个圆心距离为 d，若两个圆是包含关系，则需要满足 d+r < R。

代码如下。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define p_q priority_queue
#define pb push_back
#define mk make_pair
#define pii pair<int,int> 
#define ve vector
#define endl '\n'
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define eps 1e-10
#define lowbit(x) (x&(-x))
namespace cute_fzj_kuai_ruarua{
    double dis(int x,int y,int xx,int yy){
        return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
    }
    int k;
    int n,m;
    int x[55],y[55];
    void main(){
        cin>>k>>n>>m;
        for(int i=1;i<=k;i++){
            cin>>x[i]>>y[i];
        }
        int ans=0;
        for(int A=1;A<=k;A++){
            for(int B=1;B<=k;B++){
                for(int C=1;C<=k;C++){
                    for(int D=1;D<=k;D++){
                        if(A==B||A==C||A==D||B==C||B==D||C==D) continue;
                        double r=dis(x[A],y[A],x[B],y[B]);
                        double R=dis(x[C],y[C],x[D],y[D]);
                        if(x[A]-r<-eps||x[A]+r-n>eps||y[A]-r<-eps||y[A]+r-m>eps) continue;
                        if(x[C]-R<-eps||x[C]+R-n>eps||y[C]-R<-eps||y[C]+R-m>eps) continue;
                        if(eps<r-R-dis(x[A],y[A],x[C],y[C])) ans++;
                    }
                }
            }
        }
        cout<<ans;
    }
} 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cute_fzj_kuai_ruarua::main(); 
    return 0;
}