描述

传送门：D-Thinking Bear magic

In order to become a magical girl, Thinking-Bear are learning magic circle.
He first drew a regular polygon of N sides, and the length of each side is a.
He want to get a regular polygon of N sides, and the polygon area is no more than L.
He doesn’t want to draw a new regular polygon as it takes too much effort.
So he think a good idea, connect the midpoint of each edge and get a new regular polygon of N sides.
How many operations does it need to get the polygon he want?

输入描述

The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.
The first line of each case contains three space-separated integers N, a and L (3 ≤ N ≤ 10, 1 ≤ a ≤ 100, 1 ≤ L ≤ 1000).

输出描述

For each test case, output a single integer.

示例

输入

1
2

1
4 2 3

输出

题解

题目大意

给出一个正多边形和多边形的每一条边的边长，然后给出一个面积，求每次在正多边形的的边取中点，然后连接各个中点，形成一个新的正多边形，问经过几次这次这样的操作后能使面积小于L。

思路

计算几何，关键是操作后的面积与原面积比为 $ \cos ^{2}\left( 180^{\circ }\div n\right) $ ，坑点是double的精度问题。

扩展

内角:正n边形的内角和度数为：（n－2)×180°;正n边形的一个内角是 (n-2)×180°÷n.

外角:正n边形外角和等于n·180°－(n－2)·180°=360°,所以正n边形的一个外角为： 360°÷n.
所以正n边形的一个内角也可以用这个公式： 180°-360°÷n.

中心角：任何一个正多边形，都可作一个外接圆，多边形的中心就是所作外接圆的圆心，
就是这条边所对的弧的圆心角，因此这个角就是360度÷边数。正多边形中心角：360°÷n
因此可证明，正n边形中，外角= 中心角= 360°÷n

对角线：在一个正多边形中，所有的顶点可以与除了他相邻的两个顶点的其他顶点连线，就
成了相邻的点）个三角形。三角形内角和：180度，所以把边数减2乘上180度，就是这个正多
边形的内角和。

面积：设正n边形的半径为R，边长为an，中心角为αn，边心距为rn，则αn=360°÷n，
an=2Rsin(180°÷n)，rn=Rcos(180°÷n)，R^2=r n^2+(an÷2)^2，周长pn=n×an，面积
Sn=pn×rn÷2。

代码

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const double eps = 1.0e-6;

int main(){
    int T;
    cin>>T;
    while(T--){
        double n,a,l;
        scanf("%lf %lf %lf",&n,&a,&l);
        int ans=0;
        double R=a/(2.0*sin((180.0/n)*PI/180.0));
        double S=0.5*sin((360.0/n)*PI/180.0)*n*R*R;
        double an=180.0*(n-2)/n;
        while(S > l && fabs(S-l) > eps){
            S = S*cos(((180.0-an)/2.0)*PI/180.0)*cos(((180.0-an)/2.0)*PI/180.0);
            ans++;
        }
        cout << ans << endl;
    }
}