圆的国度 题解

题目大意

给定若干个圆的半径与具体位置，求从一个点走到另一个点至少要穿过几条圆的边界。

思路分析

没说走直线，说明随便走。

但是有两点是一定的：

• 在圆内的点走到圆外的点一定要穿过一条圆的边界。
• 在圆外的点走到圆内的点一定要穿过一条圆的边界。

所以我们可以进行分类：

1. 该圆外到该圆内：1条
2. 另一圆内到该圆内：2条
3. 该圆内到该圆内：0条
4. 该圆外到该圆外：1条

那么该如何判断是否在圆内呢？只需判断一点到圆心的距离是否小于半径。是就是在，不是就是不在。

距离即采用勾股定理所定义的直线距离来计算。

代码

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define IL inline
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct Node
{
	int num[3];	//存储相关数据
}p[N];
bool f[N];//第一个点是否在某个圆内
bool flag(int x, int y, int i)
{
	double xx = x - p[i].num[0];
	double yy = y - p[i].num[1];
	if(p[i].num[2] > sqrt(xx * xx + yy * yy))//半径 > 一点到圆心的距离（保证不会在边上，不会等于）
		return true;
	return false;
} 

IL int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c <'0'|| c >'9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
    return x * f;
}

void write(int x)
{
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}


int main()
{
    int n, len = 0;
    cin >> n;
    for(int j = 0;j < 3;j++)
    {
    	for(int i = 0;i < n;i++)
    	{
    		cin >> p[i].num[j];
		}
	}
	int x, y, xx, yy;
	cin >> x >> y >> xx >> yy;
	int ans = 0;
	for(int i = 0;i < n;i++)
	{
		if(flag(x, y, i)) //第一个点判定
		{
			ans++;
			f[i] = 1;
		}
		if(flag(xx, yy, i)) // 第二个点判定
		{
			ans++;
			if(f[i] == 1) ans -= 2; // 圆内到圆内不是2，是0，进行特判。
		}
	}
	cout << ans << endl;
	return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct node{
	int num[3];
}p[N];
bool f[N];
bool flag(int x,int y,int i){
	double xx = x - p[i].num[0];
	double yy = y - p[i].num[1];
	
	if (p[i].num[2] > sqrt(xx * xx + yy * yy))
		return 1;
	return 0;
}
int main(){
	int n,len = 0;
	cin >> n;
	for (int j = 0;j<3;j++){
		for (int i = 0;i<n;i++){
			cin >> p[i].num[j];
		}
	}
	int x,y,xx,yy;
	cin >> x >> y >> xx >> yy;
	int ans = 0;
	for (int i = 0;i<n;i++){
		if (flag(x,y,i)){
			ans++;
			f[i] = 1;
		}
		if (flag(xx,yy,i)){
			ans++;
			if (f[i] == 1)
				ans-=2;
		}
	}
	cout << ans << endl;
    return 0;
}