[UESTC SC T3] 蛋糕
暂无链接
蛋糕
【题目描述】
今天是鲍勃的生日,爱丽丝打算做一个蛋糕送给他。
这是鲍勃的n 岁生日,所以爱丽丝的蛋糕必须是正n 边形。而且,鲍勃很喜
欢数字m,所以这个蛋糕必须放在一个正m 边形的盒子里。为了让气氛更加浪漫,爱丽丝将在蛋糕的中心插上一根蜡烛,显然,蜡烛既在蛋糕的中心,又在盒子的中心是最好的。
换句话说,爱丽丝应该使正n 边形的蛋糕能被容纳在正m 边形的盒子里,且
使其中心重合。事实上,爱丽丝已经做好了蛋糕,蛋糕是边长为1 的正n 边形,现在她想知道,正m 边形盒子的最小边长是多少。
【输入格式】
每组测试数据包含多行,以EOF 作为文件结束,每行包括两个正整数n 和m。
【输出格式】
输出包含多行,每行包含一个整数,代表最小的符合条件的正m 边形盒子的
边长,保留4 位小数。
【样例输入1】
4 8
【样例输出1】
0.5412
【样例输入2】
8 4
【样例输出2】
2.4142
【数据范围】
对于20%的数据,n,m≤100;
对于40%的数据,n,m≤10000;
对于60%的数据,n,m≤1000000;
对于80%的数据,n,m≤100000000;
对于100%的数据,n,m≤1000000000。
题解
考试的时候画了一页图,推了一个玄学规律,应该全WA的,然而居然得了80分,感谢成电不杀之恩,没有爆零orz。
正解是在n边形,m边形之间套一个 lcm(n,m) l c m ( n , m ) 边形,这样嵌套起来计算内部刚好是角顶上角,外面是边顶上边,就很好计算。
在下图中以正三角形和正五边形嵌套为例:
我们就可以推导公式如下:
OK=OL=KA2sin∠WOK O K = O L = K A 2 s i n ∠ W O K
OV=OKcos∠VOL O V = O K c o s ∠ V O L
ST=2OVtan∠OV S T = 2 O V t a n ∠ O V
最后整合一下,把其中的角用 π π 替换,又已知 KA=1 K A = 1 :
代码
300+Bytes码完。。。
#include<bits/stdc++.h>
#define db long double
#define ll long long
using namespace std;
ll n,m;
const db Pi=acos((db)-1);
int gcd(int a,int b)
{return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b)
{return a*b/gcd(a,b);}
void ac()
{printf("%.4Lf\n",cos(Pi/lcm(n,m))*tan(Pi/m)/sin(Pi/n));}
int main()
{
while(scanf("%lld%lld",&n,&m)!=EOF)ac();
return 0;
}