C++14(g++5.4) 解法, 执行用时: 682ms, 内存消耗: 20120K, 提交时间: 2019-01-04 14:46:24

#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-8;
const int maxn = 100010;
 
int T, cas = 1, n;
double r, a[maxn], b[maxn], c[maxn];
double area[maxn], height[maxn];
 
double f(double h)
{
    double ret = 0;
    for (int i=1;i<=n;i++)
        if (h < height[i]) ret += a[i] * (1.0 - h / height[i]);
    return ret;
}
 
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%lf", &n, &r);
        for (int i=1;i<=n;i++) scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
        for (int i=1;i<=n;i++)
        {
            double p = (a[i] + b[i] + c[i]) / 2;
            area[i] = sqrt(p * (p-a[i]) * (p-b[i]) * (p-c[i]));
            height[i] = area[i] * 2 / a[i];
        }
        double low = 0, high = 1000000, mid;
        while ( fabs(high - low) > eps )
        {
            mid = (low + high) / 2;
            if (f(mid) <= r) high = mid;
            else low = mid;
        }
        double ans = 0, h = mid;
        for (int i=1;i<=n;i++)
            if (h < height[i]) ans += a[i] * (1.0 - h / height[i]) * (height[i] - h) / 2;
        printf("%.3lf\n", ans + h * r);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 532ms, 内存消耗: 4452K, 提交时间: 2020-03-16 21:44:23

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100010;
const double eps=1e-8;
double a[maxn],b[maxn],c[maxn],h[maxn],area[maxn];
int n;
double len;
int t;
double f(double k)
{
	double ret=0;
	for(int i=1;i<=n;i++)
	{
		if(k<h[i])
		{
			ret+=a[i]*(1.0-k/h[i]);
		}
	}
	return ret;
}
int main()
{
	int i;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lf",&n,&len);
		for(i=1;i<=n;i++)
		{
			scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
			double p=(a[i]+b[i]+c[i])/2;
			area[i]=sqrt(p*(p-a[i])*(p-b[i])*(p-c[i]));
			h[i]=area[i]*2.0/a[i]; 
		}
		double mid,l=0,r=100000;
		while(fabs(r-l)>eps)
		{
			mid=(l+r)/2.0;
			if(f(mid)<=len)
			{
				r=mid;
			}
			else
			{
				l=mid;
			}
		}
		double ans=0;
		for(i=1;i<=n;i++)
		{
			if(mid<h[i])
			{
				ans+=a[i]*(1.0-mid/h[i])*(h[i]-mid)/2.0;
			}
		}
		ans+=mid*len;
		printf("%.3f\n",ans);
	}
}