题目大意
在坐标系中给定一颗满二叉树，计算它的面积。就为一个三角形加多个梯形组成。
题解
公式推导如下：
令每层高度为h，第二层宽度为a。就有第一个三角形的面积为
S
三
角
形
=
1
2
a
h
S_{三角形}=\frac{1}{2}ah
S三角形?=21?ah
同时打表得
第1层（即实际中的第三层，此处方便推导）宽度为
a
?
(
1
+
1
2
)
a*(1+\frac{1}{2})
a?(1+21?)
第2层宽度为
a
?
(
1
+
1
2
+
1
+
1
4
)
a*(1+\frac{1}{2}+1+\frac{1}{4})
a?(1+21?+1+41?)
第n层宽度为
a
?
(
1
+
1
2
+
1
+
1
4
+
.
.
.
+
1
+
1
2
n
)
a*(1+\frac{1}{2}+1+\frac{1}{4}+...+1+\frac{1}{2^n})
a?(1+21?+1+41?+...+1+2n1?)
用等比数列求和公式整理可得第i层为
2
?
1
2
i
2-\frac{1}{2^i}
2?2i1?
设该数列为an且前n项和为Sn
注意到所有梯形高度相同，所以，可以求出所有梯形的上下底之和再乘以高就能得到所有梯形的面积。
同时，可以发现本题中的梯形除了第一个和最后一个都有共用边，即所有梯形的上下底之和为
a
(
2
S
n
?
1
+
a
n
)
+
a
a(2S_{n-1}+a_{n})+a
a(2Sn?1?+an?)+a
同样用等比数列进行整理就有
a
(
4
n
+
3
2
n
?
3
)
a(4n+\frac{3}{2^n}-3)
a(4n+2n3??3)
所有梯形的面积为
a
h
2
(
4
n
+
3
2
n
?
3
)
\frac{ah}{2}(4n+\frac{3}{2^n}-3)
2ah?(4n+2n3??3)
再加上三角形的面积就为答案
a
h
2
(
4
n
+
3
2
n
?
2
)
\frac{ah}{2}(4n+\frac{3}{2^n}-2)
2ah?(4n+2n3??2)
代码
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int k;
scanf("%d",&k);
double xt,yt,xl,yl,xr,yr;
scanf("%lf%lf%lf%lf%lf%lf",&xt,&yt,&xl,&yl,&xr,&yr);
double h=abs(yl-yt);
double a=xr-xl;
double res=a*h/2*(4*(k-2)+3*pow(0.5,k-2)-2);
printf("%.3lf\n",res);
}
return 0;
}
|