HDU 4498 Function Curve(数学)

发布时间:2016-12-6 18:14:27 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4498 Function Curve(数学)",主要涉及到HDU 4498 Function Curve(数学)方面的内容,对于HDU 4498 Function Curve(数学)感兴趣的同学可以参考一下。

Function Curve Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 73    Accepted Submission(s): 18 Problem Description Given sequences of k1, k2, … kn, a1, a2, …, an and b1, b2, …, bn. Consider following function:  Then we draw F(x) on a xy-plane, the value of x is in the range of [0,100]. Of course, we can get a curve from that plane.  Can you calculate the length of this curve?   Input The first line of the input contains one integer T (1<=T<=15), representing the number of test cases.  Then T blocks follow, which describe different test cases.  The first line of a block contains an integer n ( 1 <= n <= 50 ).  Then followed by n lines, each line contains three integers ki, ai, bi ( 0<=ai, bi<100, 0<ki<100 ) .   Output For each test case, output a real number L which is rounded to 2 digits after the decimal point, means the length of the curve.   Sample Input 2 3 1 2 3 4 5 6 7 8 9 1 4 5 6   Sample Output 215.56 278.91 Hint All test cases are generated randomly.   Source 2013 ACM-ICPC吉林通化全国邀请赛——题目重现   Recommend liuyiding   这个题目题意很简单,思路也不难,难的是具体实现,和具体细节处理,由于题目数据说是随机产生,而且开始我老是wa,所以我写了一个随机产生数据的程序和 标程比对 一步步找出问题所在! 随机数据产生程序: #include <stdio.h> #include <time.h> #include <stdlib.h> int main() { printf("%d\n",15); int k; srand((unsigned)time(NULL)); for(int i=0;i<15;i++) { printf("%d\n",100); for(int j=0;j<100;j++){ k=rand()%100; if(k==0) k++; printf("%d %d %d\n",rand()%100+1,rand()%100,rand()%100); } } return 0; } 解题思路: 题目意思就是要求一段曲线的长度,首先我想到的是逼近,然后啪啪啪的写出程序,步长大了TLE步长小了wa肯定是精度问题 后来想想还是老实点求交点积分吧 然后就是求交点(只要x坐标就行了),两个抛物线的交点还是很好求的,直接解方程就行了,不过要注意排除几种无解的情况,和分母为0的无解 情况,然后添加y=100.0和所有抛物线的交点,再添加0 和 100两个点 然后对所有的x值排序,排序之后去除一些不在0-100范围内的和重复的点 经过上面操作我们就把曲线分成若干小区间,现在关键问题是每个区间的曲线到底落在那个抛物线上,或者说在y=100上 这个很容易,取相邻两点的中点,带入一个个抛物线方程,看哪个对应的y最小,如果最小的都还是大于100说明这个点一定 落在y=100上!之后就是积分计算了! 为什么这样,其实交点已经把曲线分成最小连续区间了! #include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> #include <cmath> using namespace std; #define maxn 150 #define inf 1e14 #define eps 1e-8 bool zero(double x){ return fabs(x) < eps; } double cross[maxn*maxn]; int belong[maxn*maxn]; double k[maxn],a[maxn],b[maxn]; int n,pos; bool cmp(const double &a,const double &b){ return a<b; } int cal_cross(){ double temp1,temp2,temp3; int nu; for(int i=0;i<n;i++)//求所有抛物线的交点 for(int j=i+1;j<n;j++){ if(k[i]==k[j] && a[i]==a[j])//无解1 continue; temp1=2*a[i]*k[i],temp2=2*a[j]*k[j]; temp3=(temp2-temp1)*(temp2-temp1)-4*(k[i]-k[j])*(k[i]*a[i]*a[i]+b[i]-k[j]*a[j]*a[j]-b[j]); if(temp3 < 0 || zero(k[i]+k[i]-k[j]-k[j]))//无解2 continue; temp3=sqrt(temp3); cross[pos++]=((temp1-temp2)+temp3)/(k[i]+k[i]-k[j]-k[j]); cross[pos++]=((temp1-temp2)-temp3)/(k[i]+k[i]-k[j]-k[j]); } for(int i=0;i<n;i++)//求y=100和所有抛物线的交点 cross[pos++]=sqrt((100.0-b[i])/k[i])+a[i],cross[pos++]=a[i]-sqrt((100.0-b[i])/k[i]); cross[pos++]=0,cross[pos++]=100;//添加端点 sort(cross,cross+pos,cmp); nu=0; if(cross[0] >=0) nu=1; for(int i=1;i<pos;i++){//去除重复和越界点 if(cross[i] < 0 || cross[i]>100 || zero(cross[i]-cross[i-1])) continue; cross[nu++]=cross[i]; } pos=nu; return 0; } double calc(double x){//积分 return x*sqrt(1+x*x)/2 + log(x+sqrt(1+x*x))/2; } int solve(){ int i,j,Min_pos; double mid,now,re,ans; cal_cross(); for(i=1;i<pos;i++){//判断当前曲线属于哪条抛物线或者y=100 mid=(cross[i]+cross[i-1])/2; now=inf; Min_pos=0; for(j=0;j<n;j++){ re=k[j]*(mid-a[j])*(mid-a[j])+b[j]; if(now > re) now=re,Min_pos=j; } if(now > 100.0) belong[i]=-1; else belong[i]=Min_pos; } ans=0; for(i=1;i<pos;i++){//计算结果 if(belong[i]==-1){ ans+=cross[i]-cross[i-1];} else{ ans += (calc(2*k[belong[i]]*(cross[i]-a[belong[i]]))-calc(2*k[belong[i]]*(cross[i-1]-a[belong[i]])))/(2*k[belong[i]]); } } printf("%.2lf\n",ans); return 0; } int main(){ int t,i,j; scanf("%d",&t); while(t--){ scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf%lf%lf",&k[i],&a[i],&b[i]); pos=0; solve(); } return 0; }

上一篇:130823创建过程
下一篇:启动Java程序的时候如何检测用户的电脑上是否装了Java虚拟机

相关文章

相关评论