luogu P4986【逃离】

乱搞真是好玩，牛顿迭代不存在的。。。

传送门

首先解释题意：圆的边界就是出口，想要同时到达圆的边界速度就要一样，三个矢量要构成一个直角三角形，那么就是说让你找一个x满足$c^2(x)=a^2(x)+b^2(x)$。

设$f(x)=c^2(x)-a^2(x)-b^2(x)$，那么就是求$f$在$[l,r]$范围里的零点。

首先谁都知道FFT求出f，我不说废话了。

然后如果你知道一个区间$[l,r]$满足$f(l)\times f(r)<=0$，这个区间一定至少有一个零点。二分就是了，不想讲二分，附上二分代码：

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 (f(mid)>0.0){if (ta) l=mid; else r=mid;}
    else{if (ta) r=mid; else l=mid;}
}
return mid;

那么我们怎么找到两个异号的点呢？模拟退火找！没了！

#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;
    }
//	printf("%.8lf %.8lf\n",res,kin);
    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];
//	printf("%d\n",maxn);
//	for (int i=0; i<maxn; i++) printf("%.3lf ",c[i].x);
//	puts("");
    u=SA(0); v=SA(1);
    if (u<-3||v<-3){puts("Inconsistent!"); return 0;}
    printf("%.8lf",calc());
    return 0;
}