码蹄集迷宫2

一时失言乱红尘 2023-10-03 19:28 36阅读 0赞

### 一、题目：迷宫2 ###

迷宫中有N堵圆形的墙。两个人被困在迷宫的不同位置。求他们如果要相见，至少要穿过多少堵墙。保证任意两个圆不相交，不重合，也不会相切，但有可能相互包含。人的位置和墙不重合。

### 二、格式 ###

![在这里插入图片描述][a0f711d6525249b8ba8026e25cd2b731.png]

### 三、样例 ###

输入1

3
    0 0 1
    3 0 1
    2 0 4
    0 0 3 0

输出2

**备注（对于100%的数据， 0 <= N <=8000）**  
**思路：**  
给定两点a, b。 对于任意一个圆，如果a或者b只有一个在这个圆里面，则表示两者相遇一定要破坏这堵墙。如果两者在圆内或者都在圆外，则表示他们相遇不需要破坏这堵墙。  
所以只需要对于每次圆依此判断两个点是否在圆内，如果只有一个点在圆内，则结果+1，否则遍历下一个圆。  
**注意！！！！！！**  
要判断点（a，b）是不是在(x,y)为圆心，r为半径的圆内  
若直接写

if((a - x) * (a - x) + (b - y) * (b - y) < r *r )

由于数据太大，可能会发生数据溢出的情况，所以要换成以下写法

if(double((a - x) * 1.0 / r) * (a - x) + double((b - y) * 1.0 / r) * (b - y) <= r

### 代码 ###

#include<bits/stdc++.h> 
    #define ll long long
    using namespace std;
    const int N = 1e8 + 1;
    int n;
    int x[N], y[N], r[N]; //每个圆的参数
    
    int main( )
    {
        
        int a, b, c, d;//两个点(a,b)和(c,d)
        cin >> n;
        for(int i = 0; i < n; i ++){
        
            cin >> x[i] >> y[i] >> r[i];
        }
    
        cin >> a >> b >> c >> d;
        int cnt1 = 0;//只有a点在圆内的圆的个数
        int cnt2 = 0;//只有b点在圆内的圆的个数
        int flag1 = 0, flag2 = 0;//flag表示对于某个圆，a和b是否在圆内
        for(int i = 0; i < n; i ++){
        
            flag1 = 0, flag2 = 0;
            if( double((a - x[i])*1.0 / r[i]) * (a - x[i]) + double((b - y[i])*1.0 / r[i]) * (b - y[i]) <= r[i] )
            {
        
            	//a点在圆内
                cnt1 ++;
                flag1 = 1;
            }
            if( double((c - x[i])*1.0 / r[i]) * (c - x[i]) + double((d - y[i])*1.0 / r[i]) * (d - y[i]) <= r[i] )	
            {
        
    			//b点在园内        
                cnt2 ++;
                flag2 = 1;
            }
            if(flag1 && flag2){
        
            	//a b两点都在圆内
                cnt1 --; cnt2 --;
            }
        }
    
        cout << cnt1 + cnt2 << endl;//结果就是只有一个点在圆内的圆的个数
    
        return 0;
    }

[a0f711d6525249b8ba8026e25cd2b731.png]: https://img-blog.csdnimg.cn/a0f711d6525249b8ba8026e25cd2b731.png