1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
| #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; const double Pi=acos(-1.0); struct complex{ double x,y; complex (double xx=0,double yy=0){x=xx,y=yy;} }a[400001],b[400001],c[400001]; double u,v,ri,le; int la,lb,lc,r[400001],l,lim,maxn; complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);} complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);} complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} inline void FFT(complex *a,int inv){ for (int i=0; i<lim; i++) if (i<r[i]) swap(a[i],a[r[i]]); for (int i=1; i<lim; i<<=1){ complex wn(cos(Pi/i),inv*sin(Pi/i)); for (int j=0; j<lim; j+=(i<<1)){ complex w(1,0); for (int k=0; k<i; k++,w=w*wn){ complex x=a[j+k],y=w*a[i+j+k]; a[j+k]=x+y; a[i+j+k]=x-y; } } } if (inv<0) for (int i=0; i<=lim; i++) a[i].x=a[i].x/(double)(lim); } inline double getans(double x){ double sum=0,p=1; for (int i=0; i<=maxn; i++) sum+=p*c[i].x,p*=x; return sum; } inline double SA(int inv){ double t=1,delta=0.995,eps=1e-5,ans=0,num=getans(0),older; double res=0,kin=num; while (t>eps){ int w=rand()%2; double dx=((rand()*1000.0)/(RAND_MAX*1000.0)); if (w) dx*=(ri-ans); else dx*=(le-ans); older=getans(ans+dx)-num; if (inv){ if (older>0||exp((double)(-older/t))*RAND_MAX>(rand()*100000.0)/100000.0){ num+=older,ans+=dx; if (num>kin) kin=num,res=ans; if (kin>0) return res; } } else{ if (older<0||exp((double)(older/t))*RAND_MAX>(rand()*100000.0)/100000.0){ num+=older,ans+=dx; if (num<kin) kin=num,res=ans; if (kin<0) return res; } } t=t*delta; }
if (((!inv)&&kin>0)||(inv&&kin<0)) return -4; return res; } double calc(){ int ta=(u>v); double eps=1e-9,mid,l=min(u,v),r=max(u,v); while (r-l>eps){ mid=(l+r)/2.0; if (getans(mid)>0.0){if (ta) l=mid; else r=mid;} else{if (ta) r=mid; else l=mid;} } return mid; } int main(){ srand(20190613); scanf("%d%d%d",&la,&lb,&lc); scanf("%lf%lf",&le,&ri); for (int i=0; i<=la; i++) scanf("%lf",&a[i].x); lim=1; while (lim<=la+la) lim<<=1,l++; for (int i=0; i<lim; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); FFT(a,1); for (int i=0; i<=lim; i++) a[i]=a[i]*a[i]; FFT(a,-1); maxn=max(maxn,lim); memset(r,0,sizeof(r)); for (int i=0; i<=lb; i++) scanf("%lf",&b[i].x); l=0; lim=1; while (lim<=lb+lb) lim<<=1,l++; for (int i=0; i<lim; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); FFT(b,1); for (int i=0; i<=lim; i++) b[i]=b[i]*b[i]; FFT(b,-1); maxn=max(maxn,lim); memset(r,0,sizeof(r)); for (int i=0; i<=lc; i++) scanf("%lf",&c[i].x); l=0; lim=1; while (lim<=lc+lc) lim<<=1,l++; for (int i=0; i<lim; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); FFT(c,1); for (int i=0; i<=lim; i++) c[i]=c[i]*c[i]; FFT(c,-1); maxn=max(maxn,lim); for (int i=0; i<=maxn; i++) c[i]=c[i]-a[i]-b[i];
u=SA(0); v=SA(1); if (u<-3||v<-3){puts("Inconsistent!"); return 0;} printf("%.8lf",calc()); return 0; }
|