nyoj 2357 插塔憋憋乐"/>
nyoj 2357 插塔憋憋乐
插塔憋憋乐
题目链接:插塔憋憋乐
题目描述
众所不知,LLM是一位红警3大佬,打的非常厉害,但是曾经也是一位萌新,喜欢在家里放防御塔,然后攒单位。现在是这样的:
LLM有一个半径为R的基地,他想放一些防御塔,让任何一个敌方单位在进入自己基地的开始就受到防御塔的攻击,由于LLM希望敌人会顶着防御塔的攻击伤害自己,所以他希望任何一个敌人进入自己基地的时候就立刻受到至少两个防御塔的攻击,现在已知防御塔的防御半径为r,为了简化问题,我们假设:
1.如果一个敌人经过两个防御塔的防御的范围相切的点(如图所示),会受到两个防御塔的攻击,这里受到两个防御塔的伤害
2.不需要保证基地内部受到保护,只要保证敌人在进入基地时受到防御塔攻击即可请问最少需要几个防御塔
输入
每个测试文件少于1000组测试样例
每组测试样例包含两个整数R,r
1<=R,r<=500
输出
输出仅包含一个数字,代表需要的防御塔数量
样例输入
1 1
样例输出
2
思路:
先考虑简化版本:
如果只需要保证受到一个防御塔的伤害怎么办?
思考后可以发现,对于一个防御塔而言,它若是想得到最佳的利用那么它的直径的两个端点落在基地周长上面时即可,因此我们可以计算出来只受到一个防御塔伤害时的最少防御塔数量(假设为 n)
那么受到两个防御塔的伤害则只需要2n即可
代码:
#include<stdio.h>
#include<math.h>const double PI=acos(-1.0);
const double eps=1e-6;int main()
{int R,r;while(~scanf("%d%d",&R,&r)){if(r>=R){printf("2\n");continue;}double tot=PI/asin(r*1.0/R)*2;int ans=(int)tot;if(tot-ans>eps)++ans;printf("%d\n",ans);}return 0;
}
更多推荐
nyoj 2357 插塔憋憋乐
发布评论