计算几何 - 圆 - 洛谷 P1652

计算几何 - 圆 - 洛谷 P1652

给 出 n 个 圆 , 保 证 任 意 两 个 圆 都 不 相 交 。 然 后 给 出 两 个 点 ( x 1 , y 1 ) , ( x 2 , y 2 ) ， 保 证 均 不 在 某 个 圆 上 ， 要 从 ( x 1 , y 1 ) − > ( x 2 , y 2 ) 画 条 曲 线 ， 问 这 条 曲 线 最 少 穿 过 多 少 次 圆 的 边 界 ？ 给出n个圆,保证任意两个圆都不相交。 然后给出两个点(x_1,y_1),(x_2,y_2)，\\保证均不在某个圆上，要从(x_1,y_1)->(x_2,y_2)画条曲线，问这条曲线最少穿过多少次圆的边界？ 给出n个圆,保证任意两个圆都不相交。然后给出两个点(x1​,y1​),(x2​,y2​)，保证均不在某个圆上，要从(x1​,y1​)−>(x2​,y2​)画条曲线，问这条曲线最少穿过多少次圆的边界？

输入格式

第一行为一个整数 n，表示圆的个数；

第二行是 n 个整数，表示 n 个圆的 x 坐标；

第三行是 n 个整数，表示 n 个圆的 y 坐标；

第四行是 n 个整数，表示 n 个圆的半径 r；

第五行是四个整数 x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2 x1​,y1​,x2​,y2​

输出格式

仅一个整数，表示最少要穿过多少次圆的边界。

输入输出样例

输入：

7
1 -3 2 5 -4 12 12
1 -1 2 5 5 1 1
8 1 2 1 1 1 2
-5 1 12 1

输出：

3

数据范围

对 于 100 % 的 数 据 ， 1 ≤ n ≤ 50 ， ∣ x ∣ , ∣ y ∣ ≤ 1000 ， 1 ≤ r ≤ 1000 。 保 证 圆 之 间 没 有 公 共 点 。 对于 100\% 的数据，1\le n \le 50，|x|,|y| \le 1000，1 \le r \le1000。 保证圆之间没有公共点。 对于100%的数据，1≤n≤50，∣x∣,∣y∣≤1000，1≤r≤1000。保证圆之间没有公共点。

---

分析：

① 、 首 先 考 虑 特 殊 情 况 ： ①、首先考虑特殊情况： ①、首先考虑特殊情况：

当 两 点 在 同 一 个 小 圆 内 部 或 者 两 个 点 都 未 被 任 何 圆 包 含 ， 此 时 输 出 0. \qquad 当两点在同一个小圆内部或者两个点都未被任何圆包含，此时输出0. 当两点在同一个小圆内部或者两个点都未被任何圆包含，此时输出0.

② 、 一 般 情 况 ： ②、一般情况： ②、一般情况：

当 其 中 一 个 点 被 某 个 圆 包 围 时 ， 我 们 可 将 整 个 圆 视 作 一 个 ′ ′ 大 点 ′ ′ ， 如 下 图 \qquad 当其中一个点被某个圆包围时，我们可将整个圆视作一个''大点''，如下图 当其中一个点被某个圆包围时，我们可将整个圆视作一个′′大点′′，如下图

在 两 个 ′ ′ 大 点 ′ ′ 之 间 连 线 ， 无 需 穿 过 任 何 边 界 ， 在两个''大点''之间连线，无需穿过任何边界， 在两个′′大点′′之间连线，无需穿过任何边界，

而 对 ′ ′ 小 点 ′ ′ A 而 言 ， 至 少 穿 过 2 层 边 界 才 能 与 B 相 连 ， 对 小 点 ′ ′ B ′ ′ 而 言 ， 至 少 穿 过 1 层 边 界 才 能 与 A 相 连 。 而对''小点''A而言，至少穿过2层边界才能与B相连，对小点''B''而言，至少穿过1层边界才能与A相连。 而对′′小点′′A而言，至少穿过2层边界才能与B相连，对小点′′B′′而言，至少穿过1层边界才能与A相连。

事 实 上 ， 对 于 任 意 一 个 圆 ， 若 A 、 B 两 点 在 该 圆 的 两 侧 ， 则 至 少 要 穿 过 这 层 边 界 才 能 在 A 、 B 间 连 线 。 事实上，对于任意一个圆，若A、B两点在该圆的两侧，则至少要穿过这层边界才能在A、B间连线。 事实上，对于任意一个圆，若A、B两点在该圆的两侧，则至少要穿过这层边界才能在A、B间连线。

于 是 ， 问 题 转 化 为 ， 统 计 有 多 少 个 圆 ， 将 A 、 B 两 点 划 分 在 圆 的 内 外 两 侧 。 于是，问题转化为，统计有多少个圆，将A、B两点划分在圆的内外两侧。 于是，问题转化为，统计有多少个圆，将A、B两点划分在圆的内外两侧。

我 们 仅 需 保 证 ， 一 个 点 到 圆 心 的 距 离 小 于 半 径 ， 另 一 个 点 到 圆 心 的 距 离 大 于 半 径 ， 即 可 满 足 条 件 。 我们仅需保证，一个点到圆心的距离小于半径，另一个点到圆心的距离大于半径，即可满足条件。 我们仅需保证，一个点到圆心的距离小于半径，另一个点到圆心的距离大于半径，即可满足条件。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int N=55;

struct Point
{
    double x,y,r;
}V[N];

int n;
Point a,b;

double get_dis(Point a,Point b) //两点之间的距离
{
    double dx=a.x-b.x, dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>V[i].x;
    for(int i=0;i<n;i++) cin>>V[i].y;
    for(int i=0;i<n;i++) cin>>V[i].r;
    cin>>a.x>>a.y>>b.x>>b.y;
    
    int cnt=0;
    for(int i=0;i<n;i++)
        if((get_dis(a,V[i])<V[i].r) ^ (get_dis(b,V[i])<V[i].r)) cnt++;
    
    cout<<cnt<<endl;
    
    return 0;
}