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

思路：

由于

n \le 50

，数据范围非常小，所以这道题可以直接愉快地四层循环枚举四个点

A,B,C,D

。

设：

$\text{dis} (X,Y)$ 为点 $X$ 与点 $Y$ 的距离。
$r_1 = \text{dis} (A,B)$ ，以点 $A$ 为圆心、点 $B$ 为圆上点。
$r_2 = \text{dis} (C,D)$ ，以点 $C$ 为圆心、点 $D$ 为圆上点。
$x,y$ 为圆心的坐标。

发现:

要使小圆被大圆完全包含，则： $AC + r_2 < r_1$ 。
要使圆心到矩形边界的最小距离必须不小于半径，则： $r \le \min(x,W-x,y,H-y)$ 。

于是，思路就很明确了：

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

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

Code

CPP

#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;
}

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

文章操作

思路：

相关推荐

评论

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