Title Link: Click to enter

subject

meaning of the title

The k-layer perfect binary tree gives you the coordinates of the root node and the coordinates of the left and right sons of the root node, so that you can find the area of the convex hull formed by all nodes of the k-layer perfect binary tree (that is, the graphic area wrapped by the outermost layer).

thinking

Think about it. The total area should be the area of a top triangle plus k - 2 trapezoids. The lower side of the top triangle is also the upper side of the next trapezoid, and the lower side of the next trapezoid is the upper side of the next trapezoid. There is a connection between them. Looking at the figure, we can probably think that the distance between two adjacent points on the next floor is half the distance between two adjacent points on this floor, and the number of points on the next floor is twice the number of points on this floor, because the distance between two adjacent points on each floor is equal, so if there are n points on a floor, there are n - 1 intervals, and each interval is of equal length, Assuming the length is len, the length of this layer is equal to (n - 1) * len. Then the length of the next layer is equal to (2 * n - 1) * (len / 2). In this way, the length of each layer can be obtained recursively. The length of each layer can be regarded as the upper and lower bottom edges, and the height remains unchanged. When recursing the length of each layer, the area of the trapezoid with this layer as the upper and bottom is calculated incidentally.
In addition, it finally requires the accuracy of 1e - 3, and the maximum interval length is 2e4, every time / 2. So many times, except for a few times, the length will become very small. In the end, the length is almost unchanged, and the area of the trapezoid is equivalent to unchanged. Then we can find a precision bound. If the length is less than this bound and we haven't finished recursion, we don't need recursion, because at this time, we default that the trapezoidal area will not change, so we can directly add the remaining trapezoidal area and jump out of recursion.
(accuracy 1e - 12 is enough, do not use long double, it will cause T)

code

//#pragma GCC optimize(3)//O3
//#pragma GCC optimize(2)//O2
#include<iostream>
#include<string>
#include<map>
#include<set>
//#include<unordered_map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131 
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define lowbit(x) x & -x
#define inf 0x3f3f3f3f
//#define int long long
//#define double long double
//#define rep(i,x,y) for(register int i = x; i <= y;++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const int maxn=1e6+10;
const int mod=998244353;
const double eps=1e-12;
const int N=5e3+10;
/*--------------------------------------------*/
inline int read()
{
    int k = 0, f = 1 ;
    char c = getchar() ;
    while(!isdigit(c)){if(c == '-') f = -1 ;c = getchar() ;}
    while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48 ,c = getchar() ;
    return k * f ;
}
/*--------------------------------------------*/

int t,k;
double xt,yt,xl,yl,xr,yr;

int main() 
{
//    ios::sync_with_stdio(false);
//    cin.tie(0);cout.tie(0);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        scanf("%lf%lf%lf%lf%lf%lf",&xt,&yt,&xl,&yl,&xr,&yr);
        double dis=xr-xl,h=yt-yl,sum=2;
        double ans=dis*h/2.0,res;
        for(int i=3;i<=k;i++)
        {
            res=((sum-1)*dis+(sum*2-1)*dis/2.0)*h/2.0;
            ans=ans+res;
            sum=sum*2.0;
            dis=dis/2.0;
            if(dis<eps)
            //Here, don't be equal to, will wa, I will wa, people are stupid, or the boundary is a little smaller
            {
                ans=ans+(k-i)*res;
                break;
            }
        }
        printf("%.3lf\n",ans);
    }    
    return 0;
}