蓝桥杯省赛模拟题信号覆盖

2023-11-02

题目大意

小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 ( 0 , 0 ) (0,0) (0,0) ，东南角坐标为 ( W , 0 ) (W,0) (W,0) ，西北角坐标为 ( 0 , H ) (0,H) (0,H) ，东北角坐标为 ( W , H ) (W,H) (W,H) 。其中 W , H W, H W,H 都是整数。他在 n n n 个位置设置了信号塔，每个信号塔可以覆盖以自己为圆心，半径为 R R R 的圆形（包括边缘）。

为了对信号覆盖的情况进行检查，小蓝打算在区域内的所有横纵坐标为整数的点进行测试，检查信号状态。其中横坐标范围为 0 0 0 到 W W W ，纵坐标范围为 0 0 0 到 H H H ，总共测试 ( W + 1 ) × ( H + 1 ) (W+1)×(H+1) (W+1)×(H+1) 个点。

给定信号塔的位置，请问这 ( W + 1 ) × ( H + 1 ) (W+1)×(H+1) (W+1)×(H+1) 个点中有多少个点被信号覆盖。

输入第一行包含四个整数 W , H , n , R W,H,n,R W,H,n,R ，相邻整数之间使用一个空格分隔。

接下来 n n n 行，每行包含两个整数 x , y x,y x,y ，表示一个信号塔的坐标。信号塔可能重合，表示两个信号发射器装在了同一个位置。

输出一行包含一个整数，表示答案。

对于所有评测用例， 1 ≤ W , H ≤ 100 , 1 ≤ n ≤ 100 , 1 ≤ R ≤ 100 , 0 ≤ x ≤ W , 0 ≤ y ≤ H 1 ≤ W, H ≤ 100, 1 ≤ n ≤ 100, 1 ≤ R ≤ 100 , 0 ≤ x ≤ W , 0 ≤ y ≤ H 1≤W,H≤100,1≤n≤100,1≤R≤100,0≤x≤W,0≤y≤H 。

解题思路

数据范围较小，可以暴力枚举所有的点是否被覆盖，一个点是否被信号覆盖可以枚举所有的信号塔。
若有圆 C C C ，圆心为 ( a , b ) (a, b) (a,b) ，半径为 r r r ，则该圆的公式为：
( x − a ) 2 + ( y − b ) 2 = r 2 (x - a)^2 + (y - b)^2 = r^2 (x−a)2+(y−b)2=r2
根据数学知识可知，将一个点的横纵坐标带入上式

( x − a ) 2 + ( y − b ) 2 > r 2 (x - a)^2 + (y - b)^2 > r^2 (x−a)2+(y−b)2>r2 则该点在圆 C C C 外
( x − a ) 2 + ( y − b ) 2 = r 2 (x - a)^2 + (y - b)^2 = r^2 (x−a)2+(y−b)2=r2 则该点在圆 C C C 上
( x − a ) 2 + ( y − b ) 2 < r 2 (x - a)^2 + (y - b)^2 < r^2 (x−a)2+(y−b)2<r2 则该点在圆 C C C 内

AC_Code

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

using namespace std;

const int N = 1e2 + 10;

int w, h, n, r;
int X[N], Y[N];

bool check(int x, int y)
{
    for (int i = 0; i < n; ++ i )
    {
        int tx = x - X[i], ty = y - Y[i];
        tx *= tx, ty *= ty;
        if (tx + ty <= r * r)
            return true;
    }
    return false;
}

int main()
{
    cin >> w >> h >> n >> r;
    for (int i = 0; i < n; ++ i )
        cin >> X[i] >> Y[i];
    
    int res = 0;
    for (int i = 0; i <= w; ++ i )
        for (int j = 0; j <= h; ++ j )
            res += check(i, j);
    cout << res << endl;
    
    return 0;
}

Java

import java.util.Scanner;

public class main {
	
	static int w, h, n, r;
	static int[] X = new int[110];
	static int[] Y = new int[110];
	static boolean check(int x, int y)
	{
	    for (int i = 0; i < n; ++ i )
	    {
	        int tx = x - X[i], ty = y - Y[i];
	        tx *= tx;
	        ty *= ty;
	        if (tx + ty <= r * r)
	            return true;
	    }
	    return false;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		w = sc.nextInt();
		h = sc.nextInt();
		n = sc.nextInt();
		r = sc.nextInt();
		for (int i = 0; i < n; ++ i ) {
			X[i] = sc.nextInt();
			Y[i] = sc.nextInt(); 
		}
		
		int res = 0;
		for (int i = 0; i <= w; ++ i )
	        for (int j = 0; j <= h; ++ j )
	        	if (check(i, j))
	        		res ++;
		System.out.println(res);
	}
	
}

Python

def check(x, y):
    for i in range(n):
        tx = x - X[i]
        ty = y - Y[i]
        if tx * tx + ty * ty <= r * r:
            return True
    return False

X = []
Y = []
w, h, n, r = map(int, input().split())
for i in range(n):
    a, b = map(int, input().split())
    X.append(a)
    Y.append(b)

res = 0
for i in range(w + 1):
    for j in range(h + 1):
        res += check(i, j)
print(res)

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)