题目:https://acm.hdu.edu.cn/showproblem.php?pid=7046

题目来源:2021“MINIEYE杯”中国大学生算法设计超级联赛(7)

题目大概要求就是求按照给定的规则画出的图形的凸包大小。乍一看是计算几何的题目,然后再细想,其实就是一题数学推导的题目。

先画出内容,然后手动推一下边长的公式,然后就可以推出面积公式,直接计算就可以了。

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int t, k;
int x_root, y_root, xl, yl, xr, yr;

inline double qpow(double base, int n)
{

    double ans = 1;
    while (n)
    {
        if (n & 1)
        {
            ans = ans * base;
        }
        base = base * base;
        n >>= 1;
    }
    return ans;
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &k);
        scanf("%d%d%d%d%d%d", &x_root, &y_root, &xl, &yl, &xr, &yr);

        int dy = y_root - yr;
        double d = xr - xl;
        double h = (k - 1) * dy;

        double w = 0.0;

        double ans = 4 * (k - 2) + 3 * qpow(0.5, k - 2) - 2;

        ans *= 0.5 * d * dy;

        printf("%.3lf\n", ans);
    }
}

转载请注明原文:https://www.longjin666.top/?p=1128

你也可能喜欢

发表评论