yuzh的博客

❤ ECUST ❤

0%

SP18666 UVA1 - Radiation

发表于 更新于 Valine：

本题网址

数据点题目给得不好啊，可以参考这里

输入样例解释

这道题会无限读入Case，需要while循环来判断最后输入的“0”

一个case会出现这样的数据：

1 表示房屋数量n个

2 - n+1 表示房屋地址

n+2 输入两个核电站坐标并给出影响半径的个数k

n+3 - n+2+k 给出两个核电站的影响半径

之后的Case同样继续读入，直到输入“0”时停止读入

输出样例解释

输出数据格式很简单，直接

1
2
3
4
5
6
7
8
9
Case 1:
..
..
..
Case 2:
..
..
..
..

本题思路

这是一道模拟题，难度一般，用心做能做出来

先是while无限输入，然后读入房屋坐标和加油站坐标，直接记录好每个房屋和两个加油站的距离，剪枝优化。这样的话可以避免之后每个循环进行计算。然后对距离进行排序，可以方便计算与半径的距离并且快速舍去后续没有必要的计算。

接着是暴力比较半径的大小，是的话ans++

接下来看代码

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;

int n,xx1[200001],yy1[200001];
struct pp
{
	int ress1,ress2;
}ak[200001];

bool cmp(pp a,pp b) { //结构体排序
	if(a.ress1!=b.ress1) {
		return a.ress1<b.ress1;
	} 
	else
		return a.ress2<=b.ress2;
}

int hx1,hy1,r1,hx2,hy2,r2;
//hx1,hy1,r1分别为第一个核电站的横坐标、纵坐标和影响半径 hy1,hy2同理
int cases,ans,casejl;

int main()
{
	scanf("%d",&n);
	while(n!=0)//进入无限循环
	{
		casejl++;
		printf("Case %d:\n",casejl);//输出Case个数
		ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&xx1[i],&yy1[i]);
		}
		cin>>hx1>>hy1>>hx2>>hy2;
		for(int j=1;j<=n;j++)
		{
			ak[j].ress1=(xx1[j]-hx1)*(xx1[j]-hx1)+(yy1[j]-hy1)*(yy1[j]-hy1);//两点坐标距离公式
			ak[j].ress2=(xx1[j]-hx2)*(xx1[j]-hx2)+(yy1[j]-hy2)*(yy1[j]-hy2);
		}
		cin>>cases;
		sort(ak+1,ak+1+n,cmp);//排序
		for(int i=1;i<=cases;i++)
		{
			ans=0;
			scanf("%d%d",&r1,&r2);
			for(int j=1;j<=n;j++)
			{
				if(ak[j].ress1<=r1*r1 && ak[j].ress2<=r2*r2)
				{
					ans++;//输出答案
				}
				else if(ak[j].ress1>r1*r1 && ak[j].ress2>r2*r2)
                {
                    break;//因为排序过，可以直接跳过
                }
			}
			printf("%d\n",ans);//输出本轮答案
		}
		scanf("%d",&n);
	}
	return 0;
}

本题难点

  1. 题目中的输入数据需要自己猜测（PS：这题目有毒吧。。）
  2. 排序优化
  3. 注意细节

题后小结

第一个做出这题的是同学@TheUknownCreator，为我提供了题意解读，感谢帮助。顺便提醒此题没有必要进行快读，scanf速度足够解决本题。

顺便提供一下我和他一起编写出的补充数据