NOI2004 降雨量

红太狼 2021-11-10 23:28 148阅读 0赞

[\\(Problem Link\\)][Problem Link]

自适应辛普森,卡了一页的精度。。。

毒瘤。

/* @Date : 2019-07-30 07:58:53 @Author : Adscn (adscn@qq.com) @Link : https://www.cnblogs.com/LLCSBlog */ #include<bits/stdc++.h> using namespace std; #define IL inline #define RG register #define gi getint() #define gc getchar() #define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout) IL int getint() { RG int xi=0; RG char ch=gc; bool f=0; while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc; while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc; return f?-xi:xi; } template<typename T> IL void pi(T k,char ch=0) { if(k<0)k=-k,putchar('-'); if(k>=10)pi(k/10,0); putchar(k%10+'0'); if(ch)putchar(ch); } typedef long double db; const db eps = 1e-7; int n,m,w,T,V; struct line{ db x,y,len,k,L,R; }L[5010]; inline int dcmp(db a){ if(fabs(a)<(long double)eps)return 0; return a<0?-1:1; } struct inter{ db l,r; bool operator <(const inter & b)const{ if(dcmp(l-b.l)==0)return dcmp(r-b.r)<0; return dcmp(l-b.l)<0; } }c[307]; inline db f(db x) { db s=0;int p=0; for(int i=1;i<=m;++i) if(dcmp(L[i].L-x)<0&&dcmp(x-L[i].R)<0) { if(fabs(L[i].k)>eps) { db t1=(x-L[i].x)/L[i].k+L[i].y, t2=(x-L[i].x-L[i].len)/L[i].k+L[i].y; c[++p].l=max(L[i].y,min(t1,t2)); c[p].r=min(L[i].y+(L[i].R-L[i].L-L[i].len)/fabs(L[i].k),max(t1,t2)); } else return T; } if(!p)return 0; sort(c+1,c+p+1); db l=c[1].l,r=c[1].r; for (int i=2;i<=p;++i) if (dcmp(c[i].l-r)>0)s+=r-l,l=c[i].l,r=c[i].r; else r = max(c[i].r,r); s += r-l; return s; } inline db simpson(db l,db r){db mid=(l+r)/2;return (f(l)+4*f(mid)+f(r))*(r-l)/6;} db autosimpson(db l,db r,db sum) { db mid=(l+r)/2; db lsum=simpson(l,mid),rsum=simpson(mid,r); if(fabs(lsum+rsum-sum)<eps)return lsum+rsum; return autosimpson(l,mid,lsum)+autosimpson(mid,r,rsum); } void check(db x,db y,db len,db v,db t)//x初始位置 { db l=min(x,x+t*v),r=max(x+len,x+len+t*v); L[++m].L=l,L[m].R=r,L[m].k=v; L[m].x=x,L[m].y=y,L[m].len=len; if(r>w) { L[m].R=w; check(w-len,y+(w-len-x)/v,len,-v,t-(w-len-x)/v); } else if(l<-eps) { L[m].L=0; check(0,y-x/v,len,-v,t+x/v); } } int main(void) { n=gi,w=gi,T=gi,V=gi; for(int i=1;i<=n;++i) { int x=gi,l=gi,v=gi; if(v&&(x||l!=w))check(x,0,l,v,T); else L[++m].k=0,L[m].L=x,L[m].R=x+l; } printf("%.2Lf",fabs((T*w-autosimpson(0,w,simpson(0,w)))*V-0.0004)); return 0; }

转载于:https://www.cnblogs.com/LLCSBlog/p/11269180.html

[Problem Link]: https://www.luogu.org/problem/P4273