洛谷——P1652 圆

曾经终败给现在 2023-10-02 11:51 5阅读 0赞

## P1652 圆 ##

### 题目描述 ###

给出 n*n* 个圆,保证任意两个圆都不相交。  
然后给出两个点 (x\_1,y\_1),(x\_2,y\_2)(*x*1,*y*1),(*x*2,*y*2)，保证均不在某个圆上，要从 (x\_1,y\_1) \\to (x\_2,y\_2)(*x*1,*y*1)→(*x*2,*y*2) 画条曲线，问这条曲线最少穿过多少次圆的边界？

### 输入格式 ###

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

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

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

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

第五行是四个整数 x\_1,y\_1,x\_2,y\_2*x*1,*y*1,*x*2,*y*2。

### 输出格式 ###

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

### 输入输出样例 ###

**输入 \#1**复制

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

**输出 \#1**复制

### 说明/提示 ###

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

#include<bits/stdc++.h>
    using namespace std;
    struct circle{
        
        int x;
        int y;
        int r;
    }cir[55];
    int main(){
        
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
        
            cin>>cir[i].x;
        }
         for(int i=0;i<n;i++){
        
            cin>>cir[i].y;
        }
         for(int i=0;i<n;i++){
        
            cin>>cir[i].r;
        }
        int x1,y1,x2,y2;
        int ans=0;
        cin>>x1>>y1>>x2>>y2;
        for(int i=0;i<n;i++){
        
            double d1=sqrt((cir[i].x-x1)*(cir[i].x-x1)+(cir[i].y-y1)*(cir[i].y-y1));
            double d2=sqrt((cir[i].x-x2)*(cir[i].x-x2)+(cir[i].y-y2)*(cir[i].y-y2));
            if((d1<cir[i].r&&d2>cir[i].r)||(d1>cir[i].r&&d2<cir[i].r)){
        
                ans++;
            }
        }
        cout<<ans;
        return 0;
        
    }