原文链接https://www.cnblogs.com/zhouzhendong/p/SRM500-500.html
SRM500 Div1 500
没想到 double 的精度居然没有爆……
考虑以一个点为根的分形所涉及的区域是可以用一个矩形表示的。例如整个分形的区域就是 \(x\in [-27,27],y\in [0,81]\) 。
如果一个分形被要求的范围全部包含，那么是可以直接推公式求的。
如果一个分形代表的区域与询问区域无交，那么对答案无贡献。
否则就分治 3 个小矩形。
与询问矩形有交的分形区域比较少。所以时间复杂度是对的。
然后 double 居然没有被卡精度？
static const int N=505;
double ans,t;
void solve(double px,double py,int k,double x1,double y1,double x2,double y2){
if (k>30)
return;
double pmy=py+pow(t,k)/3*2;
double puy=py+pow(t,k);
double xL=px-pow(t,k+1);
double xR=px+pow(t,k+1);
if (x1<=xL&&xR<=x2&&y1<=py&&puy<=y2)
return (void)(ans+=(t*2*(500-k)+1.0/3.0)*pow(t,k));
if (xL>x2||xR<x1||py>y2||puy<y1)
return;
if (x1<=px&&px<=x2)
ans+=max(0.0,min(y2,pmy)-max(y1,py));
solve(px,pmy,k+1,x1,y1,x2,y2);
solve(pmy,-px,k+1,y1,-x2,y2,-x1);
solve(-pmy,px,k+1,-y2,x1,-y1,x2);
}
double getLength(int x1, int y1, int x2, int y2){
ans=0,t=1.0/3.0;
solve(0,0,0,x1*1.0/81.0-1e-15,y1*1.0/81.0-1e-15,x2*1.0/81.0+1e-15,y2*1.0/81.0+1e-15);
return ans*81.0;
}