题解 P2316 【[HNOI2005]分形】
PrincessQi · · 题解
0.前言
通过随机跳题跳到此题，然后就和这题杠上了。。。
1.思路
思路一：朴素想法，在所有切点间暴力建边对于每一个询问顺时针逆时针交替搜索。
时间复杂度：
思路二：不难发现此题的每组询问之间有且仅有两条路径，且这两条路径之和为路径上所有经过的圆的周长之和。
于是想到求出任意一条路径，然后使用路径上所有经过的圆的周长之和减去这条路径的长度得到另一条路径长度，再比较大小。
将每个圆看作一个点，两圆相切则连边，不难看出这是一棵树。
将最大的圆代表的点看做根节点，则其实一条路径上所有经过的圆就是这两个点的LCA所经过的点代表的圆，所以我们可以通过LCA求路径的方式快速求出使用路径上所有经过的圆的周长之和。
然后再进一步，其实两点间路径也可以通过类似的方式（比如定义一个标准方向，即在深度为偶数的圆上顺时针走，深度为奇数的圆上顺时针走）。
然后就可以发现其实一条路径可以分为五部分，即在询问中一个给定的节点（圆）由给定幅角到与它父亲节点（圆）的切点按照标准方向走的路径、这个给定的节点（圆）与它父亲节点（圆）的切点到给定的两个节点的LCA（圆）按照标准方向走的路径、在给定的两个节点的LCA（圆）上按照标准方向走的路径，另一个给定的节点（圆）与它父亲节点（圆）的切点到给定的两个节点的LCA（圆）按照逆标准方向走的路径、这个给定的节点（圆）由给定幅角到与它父亲节点（圆）的切点按照逆标准方向走的路径。
可能上一段看起来有点冗长，则咱们来看点直观的：
箭头代表这个圆的标准方向，则从
然后得到答案就很简单啦。
但是注意还有两种情况，即一个圆是另一个圆父亲的情况或在同一圆上的情况，需单独考虑，由于比较简单，留给读者自己思考其实是我懒。
下面上我冗长的代码（含注释）：
#include<bits/stdc++.h>
using namespace std;
const double pi=3.14159265358979323846;
int nex[6005],beg[6005],to[6005],r[3005],n,m,t,e,s,ee[3005];
struct T{
double x,y,sonf[15],faf,wtcl;
int d,fa[25],sn,snn,son[15];
}tree[3005];//定义节点，sonf、faf为儿子节点（圆）、父亲节点（圆）的幅角
void add(int x,int y){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}//链式前向星
double dist(int d,double x,double y){
if(x>y)return (2*pi-x+y)*r[d];
return (y-x)*r[d];
}//计算两点在尺寸为d的圆上逆时针距离
void dfs(int s){
for(int i=1;(1<<i)<=tree[s].d;i++)
tree[s].fa[i]=tree[tree[s].fa[i-1]].fa[i-1];
for(int i=beg[s];i;i=nex[i])dfs(to[i]);
}//倍增预处理
void dfs2(int s){
for(int i=1;i<=tree[s].sn;i++)
if(tree[s].d%2==0){
tree[tree[s].son[i]].wtcl=tree[s].wtcl+dist(tree[s].d,tree[s].sonf[i],tree[s].faf);
dfs2(tree[s].son[i]);
}
else {
tree[tree[s].son[i]].wtcl=tree[s].wtcl+dist(tree[s].d,tree[s].faf,tree[s].sonf[i]);
dfs2(tree[s].son[i]);
}
}//标准方向的距离预处理
int lca(int a,int b){
if(tree[a].d>tree[b].d)
swap(a,b);
for(int i=20;i>=0;i--)
if(tree[a].d+(1<<i)<=tree[b].d)
b=tree[b].fa[i];
if(a==b)return -1;
for(int i=20;i>=0;i--)
if(tree[a].fa[i]!=tree[b].fa[i]){
a=tree[a].fa[i];
b=tree[b].fa[i];
}
return tree[a].fa[0];
}//LCA
int main(){
scanf("%d%d%d",&n,&m,&t);
r[0]=1e5;
ee[0]=1e5;//ee是r的前缀和
for(int i=1;i<=n;i++)
scanf("%d",&r[i]),ee[i]=ee[i-1]+r[i];
s=1;//根节点为1
for(int i=1;i<=m;i++){
scanf("%lf%lf%d%d",&tree[i].x,&tree[i].y,&tree[i].d,&tree[i].fa[0]);//其实尺寸就相当于深度
tree[tree[i].fa[0]].son[++tree[tree[i].fa[0]].sn]=i;//记录儿子
add(tree[i].fa[0],i);//加边
}
for(int i=2;i<=m;i++){
tree[tree[i].fa[0]].snn++;
if(tree[i].x==tree[tree[i].fa[0]].x){
if(tree[i].y>tree[tree[i].fa[0]].y)tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=pi/2;
else tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=3*pi/2;
}
else{
if(tree[i].x>tree[tree[i].fa[0]].x&&tree[i].y>=tree[tree[i].fa[0]].y)tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=atan((tree[i].y-tree[tree[i].fa[0]].y)/(tree[i].x-tree[tree[i].fa[0]].x));
if(tree[i].x<tree[tree[i].fa[0]].x&&tree[i].y>=tree[tree[i].fa[0]].y)tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/(tree[i].x-tree[tree[i].fa[0]].x));
if(tree[i].x<tree[tree[i].fa[0]].x&&tree[i].y<tree[tree[i].fa[0]].y)tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/(tree[i].x-tree[tree[i].fa[0]].x));
if(tree[i].x>tree[tree[i].fa[0]].x&&tree[i].y<tree[tree[i].fa[0]].y)tree[tree[i].fa[0]].sonf[tree[tree[i].fa[0]].snn]=2*pi+atan((tree[i].y-tree[tree[i].fa[0]].y)/(tree[i].x-tree[tree[i].fa[0]].x));
}//分四个区域和平行于x轴的两种情况讨论幅角
}//求出sonf
for(int i=1;i<=m;i++)
for(int j=1;j<=tree[i].sn;j++){
if(tree[i].x==tree[tree[i].son[j]].x){
if(tree[i].y>tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=pi/2;
else tree[tree[i].son[j]].faf=3*pi/2;
}
else{
if(tree[i].x>tree[tree[i].son[j]].x&&tree[i].y>=tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=atan((tree[i].y-tree[tree[i].son[j]].y)/(tree[i].x-tree[tree[i].son[j]].x));
if(tree[i].x<tree[tree[i].son[j]].x&&tree[i].y>=tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=pi+atan((tree[i].y-tree[tree[i].son[j]].y)/(tree[i].x-tree[tree[i].son[j]].x));
if(tree[i].x<tree[tree[i].son[j]].x&&tree[i].y<tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=pi+atan((tree[i].y-tree[tree[i].son[j]].y)/(tree[i].x-tree[tree[i].son[j]].x));
if(tree[i].x>tree[tree[i].son[j]].x&&tree[i].y<tree[tree[i].son[j]].y)tree[tree[i].son[j]].faf=2*pi+atan((tree[i].y-tree[tree[i].son[j]].y)/(tree[i].x-tree[tree[i].son[j]].x));
}//分四个区域和平行于x轴的两种情况讨论幅角
}//求出faf
dfs(s);//倍增
for(int i=1;i<=tree[1].sn;i++)
dfs2(tree[1].son[i]);//求出标准方向上的距离
while(t--){
int x,y,xxx,yyy;
double ans,xx,yy,xf,yf,xh,yh,xxxx,yyyy,hh;
scanf("%d%lf%d%lf",&x,&xf,&y,&yf);
if(x==y){
printf("%.0lf\n",min(fabs(xf-yf),2*pi-fabs(xf-yf))*r[tree[x].d]/pi);
continue;
}//在同一圆上的情况
int h=lca(x,y);//求LCA
if(h==-1){
ans=0;
if(tree[x].d>tree[y].d)
swap(x,y),swap(xf,yf);
int kk;
for(int i=1;i<=tree[x].sn;i++)
if(lca(tree[x].son[i],y)==-1)kk=i;
if(tree[x].d%2==0)ans+=dist(tree[x].d,tree[x].sonf[kk],xf);
else ans+=dist(tree[x].d,xf,tree[x].sonf[kk]);
if(tree[y].d%2==0)ans+=dist(tree[y].d,yf,tree[y].faf);
else ans+=dist(tree[y].d,tree[y].faf,yf);
ans+=tree[y].wtcl;
ans-=tree[tree[x].son[kk]].wtcl;
if(ans>pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d]))ans=2*pi*(ee[tree[y].d]-ee[tree[x].d]+r[tree[x].d])-ans;
printf("%.0lf\n",ans/pi);
continue;
}//“直系血亲”的情况
for(int i=1;i<=tree[h].sn;i++){
if(lca(tree[h].son[i],x)==-1)xxx=tree[h].son[i],xxxx=tree[h].sonf[i];
if(lca(tree[h].son[i],y)==-1)yyy=tree[h].son[i],yyyy=tree[h].sonf[i];
}
if(tree[x].d%2==0)xx=dist(tree[x].d,xf,tree[x].faf);
else xx=dist(tree[x].d,tree[x].faf,xf);
if(tree[y].d%2==0)yy=dist(tree[y].d,tree[y].faf,yf);
else yy=dist(tree[y].d,yf,tree[y].faf);
xh=tree[x].wtcl-tree[xxx].wtcl;
yh=2*pi*(ee[tree[y].d-1]-ee[tree[h].d])-(tree[y].wtcl-tree[yyy].wtcl);
if(tree[h].d%2==0)hh=dist(tree[h].d,xxxx,yyyy);
else hh=dist(tree[h].d,yyyy,xxxx);
ans=xh+yh+xx+yy+hh;//分五段求和
if(ans>pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1]))ans=2*pi*(ee[tree[x].d]+ee[tree[y].d]-ee[tree[h].d]-ee[tree[h].d-1])-ans;//最后再比较大小
printf("%.0lf\n",ans/pi);//输出
}
return 0;
}