本文主要是介绍HDU - 4498 Function Curve 自适应simpson，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题意：求题目中F(x)的弧长
思路：求出各个二次函数的交点并保存起来，然进行排序，然后按各个交点求出以这个点为端点的一段最小的函数，并求出这个函数在这个区间的弧长。弧长当然可以用自适应simpson模版
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1e3;
int bext;
double k[maxn],a[maxn],b[maxn];
double han(double x){return 2*k[bext]*x+a[bext];
}
double F(double x){return sqrt(1.0+han(x)*han(x));
}
double simpson(double a,double b){double c=a+(b-a)/2;return (F(a)+4*F(c)+F(b))*(b-a)/6;
}
double asr(double a,double b,double eps,double A){double c=a+(b-a)/2;double L=simpson(a,c),R=simpson(c,b);if (fabs(L+R-A)<=15*eps) {return L+R+(L+R-A)/15.0;}return asr(a, c, eps/2, L)+asr(c,b, eps/2, R);
}
double asr(double a,double b,double eps){return asr(a,b, eps, simpson(a,b));
}
vector<double> x;
void push(double t){if (t>0.0&&t<100.0)x.push_back(t);
}
void jfc(double a,double b,double c){if(fabs(a)<1e-8&&fabs(b)<1e-8)return;double t=b*b-4.0*a*c;if (t<-1e-8)return ;if(fabs(a)<1e-8)push(-c/b);else{push((-b-sqrt(t))/2/a);if (t>1e-8)push((-b+sqrt(t))/2/a);}
}
int main(int argc, const char * argv[]) {int t,n;cin>>t;while (t--) {cin>>n;double ans=0;for (int i=1; i<=n; ++i){cin>>k[i]>>a[i]>>b[i];b[i]=k[i]*a[i]*a[i]+b[i];a[i]=-2*a[i]*k[i];}x.clear();x.push_back(0.0);x.push_back(100.0);k[0]=a[0]=0,b[0]=100.0;for (int i=0; i<n; ++i)for (int j=i+1; j<=n; ++j)jfc(k[j]-k[i],a[j]-a[i],b[j]-b[i]);int s=x.size();sort(x.begin(), x.end());// for (int i=0; i<s; ++i) {// cout<<x[i]<<" ";//}// cout<<endl;double xie=101;for (int i=0; i<s-1; ++i) {double t=101;for (int j=0;j<=n; ++j) {double tt=k[j]*x[i]*x[i]+a[j]*x[i]+b[j];if (fabs(t-tt)<=1e-8||t>tt) {double xx=2*k[j]*x[i]+a[j];if (fabs(t-tt)<1e-8&&(xie+1e-8)<=xx)continue;bext=j;t=tt;xie=xx;}}//cout<<bext<<endl;ans+=asr(x[i],x[i+1],1e-8);}printf("%.2f\n",ans);}return 0;
}这篇关于HDU - 4498 Function Curve 自适应simpson的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
