欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Fall with Trees 二维平面直角坐标系-凸包-推公式

程序员文章站 2022-04-04 11:09:11
...

题意 :

  • 二维平面直角坐标系中,给出根节点和左右子节点的坐标,按照规范画k层满二叉树并求凸包面积

思路 :

  • 将每一层的梯形转化为三角形。
  • 将pow换成qmi反而会inf,每一组样例中只需要一次所以可以pow。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#define endl '\n'
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
const double pi = acos(-1);
typedef long long ll;

int main()
{
//    IOS;
    
    int T;
    scanf("%d", &T);
    
    while (T -- )
    {
        int k;
        scanf("%d", &k);
        int x1, y1, x2, y2, x3, y3;
        scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
        double x = (x3 - x2) / 2.0, y = (y1 - y2) * 1.0;
        printf("%.3lf\n", 4 * x * y * (k - 2.5 + 3.0 * pow(0.5, k)));
    }
    
    return 0;
}