题解：P15056 [UOI 2023 II Stage] Unenslaved puppy

zszl · 2026-01-26 20:26:24 · 题解

前言

下文的【思路】、【解法】、【注意事项】和【代码】均采用 C++23 的标准。

洛谷题目

解法

来给大家手推一下圆的方程。

先是由勾股定理——a^2+b^2=c^2 得到斜边的表示法。接着我们把 x 坐标作为 a，y 坐标作为 b，带入，得到原点为中心的圆的方程：

注意到，我们把 x-a 带入，可以得到向 x 正方向平移的图像，y 坐标同理。因此，我们可以把 x-a 和 y-b 带入公式 \text{C(x,y,r)}，然后就得到了著名的圆的方程：

以 (a,b) 为圆心的正圆的方程为：

\boxed{(x-a)^2+(y-b)^2\le r^2}

带入题目中 a=pos_i, b=0, r=r_i 和只取半圆，得：“(x, y) 在第 i 个保护罩内”这个命题等价于如下命题：

直接计算狗和蜜蜂是否在保护罩内即可。

代码

#define p1 first
#define p2 second
#define up(i,st,nd) for(int i=(st);i<(nd)+1;++i)

#define square(i) ((i)*(i))
#define chk(x,y,pos,r) ((square((x)-(pos))+square(y)<square(r)+1)&&y>-1) // 都是整数，a<=b 等价于 a<b+1，可以快一点，>= 同理

constexpr int MAXN = 1e3 + 5;
bool d, b;
int n, pos, r;
pii dog, bee;

signed main() {
    ios::sync_with_stdio(false), ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); clock_t timr_start = clock();

    read(n, dog.p1, dog.p2, bee.p1, bee.p2);

    up(i, 1, n) {
        read(pos, r);
        d = chk(dog.p1, dog.p2, pos, r);
        b = chk(bee.p1, bee.p2, pos, r);
        if (d ^ b) { // 不同时满足
            writel("NO");
            write(i);
            return 0;
        }
    }    
    write("YES");

    cerr << "time use " << (clock() - timr_start) << "ms.";
    return 0;
}