C++14(g++5.4) 解法, 执行用时: 23ms, 内存消耗: 608K, 提交时间: 2019-09-24 17:51:25

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+100;
const int MOD=1e9+7;
const double PI=acos(-1);
typedef long long ll;
int n;
double A[60],B[60],K[60];
double F(double x)
{
    double ans=100,res=0;
    for(int i=1;i<=n;i++)
    {
        if(K[i]*(x-A[i])*(x-A[i])+B[i]<ans)
        {
            ans=K[i]*(x-A[i])*(x-A[i])+B[i];
            res=2*K[i]*(x-A[i]);
            if(K[i]*(x-A[i])*(x-A[i])+B[i]>100)res=0;
        }
    }
    return sqrt(1+res*res);
}
double simpson(double a,double b)
{
	double c=a+(b-a)/2;
    return (F(a)+4*F(c)+F(b))*(b-a)/6;   //F(x)是被积分的函数
}
double asr(double a,double b,int dep,double eps,double A)
{
	double c=a+(b-a)/2;
	double L=simpson(a,c);
	double R=simpson(c,b);
	if(dep>=10&&fabs(L+R-A)<=15*eps)return L+R+(L+R-A)/15.0;
	return asr(a,c,dep+1,eps/2,L)+asr(c,b,dep+1,eps/2,R);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&K[i],&A[i],&B[i]);
    printf("%.2lf\n",asr(0,100,0,1e-8,simpson(0,100)));
    return 0;
}

C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 396K, 提交时间: 2021-05-08 22:45:39

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double db;
typedef long long ll;
const db eps=1e-8;
int n,cnt;
db a[110],b[110],k[110]; 
db f(db x){
	db t=100;
	int i,j,id=0;
	for(i=1;i<=n;i++)
	{
		db now=k[i]*(x-a[i])*(x-a[i])+b[i];
		if(now<t) t=now,id=i;
	}
	t= 2*k[id]*(x-a[id]);
	return sqrt(1.0 + t*t);
}
db simpson(db l,db r)
{
	db mid=(l+r)/2.0;
	return (r-l)*(f(l)+4*f(mid)+f(r))/6.0;
}
db asr(db l,db r,db s,db EPS,int dep)
{
	db mid=(l+r)/2.0;
	db left=simpson(l,mid);
	db right=simpson(mid,r);
	if(dep>=10&&abs(left+right-s)<=eps*15) return left+right+(left+right-s)/15;
	return asr(l,mid,left,EPS/2,dep+1)+asr(mid,r,right,EPS/2,dep+1);
}
int main()
{
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++)
		scanf("%lf%lf%lf",&k[i],&a[i],&b[i]);
	db l=0,r=100;
	db ans=asr(l,r,simpson(l,r),eps,1);
	printf("%.2f\n",ans); 
	return 0;
}