ZOJ - 3993 - Safest Buildings （数学）

参考：https://blog.csdn.net/KuHuaiShuXia/article/details/78408194

题意：

描述了吃鸡刷圈的问题，给出楼的坐标点，和两次刷圈的半径R和r，现在寻找最安全的地方

思路：

判定安全方法：每个点以r为半径画圆，与以原点为圆心，半径为R的圆的重合部分的大小为比较基准

那么问题又转化为与原点的距离

如果R>2r，那么以大圈圆心为圆心的R-2r范围内的建筑的安全概率是相等的。

反之，以大圈圆心为圆心的2*r-R范围内的建筑的安全概率是相等的。

我们只需要判断是否是一致概率，然后添加到结果集合，使用vector

代码：

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

int main() {

	int t, n, R, r;

	scanf("%d", &t);

	while(t--) {

		vector<int> vi;

		int x, y, d, inf = 0xf3f3f3f, tmp;

		scanf("%d %d %d", &n, &R, &r);

		if(R >= 2*r) d = R - 2*r;

		else d = 2*r - R;

		for(int i = 1; i <= n; i++) {

			scanf("%d %d", &x, &y);

			if(x*x+y*y <= d*d) tmp = 0;

			else tmp = x*x+y*y;

			if(tmp < inf) {

				inf = tmp;//更新最小

				vi.clear();

			}

			if(tmp == inf) vi.push_back(i);

		}

		printf("%d\n", vi.size());

		for(int i = 0; i < vi.size(); i++) {

			printf("%d%c", vi[i],i==vi.size()-1?'\n':' ');

		}

	}

	return 0;

}

巴特西

ZOJ - 3993 - Safest Buildings （数学）

题意：

思路：

代码：

最新文章

热门文章