改编（魔改）自SNOI2017炸弹。
原题是链上的情况，这里我随手扩展到了平面上发现结果非常有趣。
先说结论，我只搞出了一个$O(nlog^2 n)$的做法，常数还大到飞起，不得不开2秒时限。
首先很明显，建图，缩点，dp。
原题的$O(n)$建图为单调栈，每个点的入边为左右两侧能炸到自己的最近点。
就是对每个$i$找满足以下条件：
的$j$中$x_j$最大的$j$。
这是一个二维偏序问题，但是由于第二式子关于第一个式子有单调性，所以可以单调栈维护。
对于本题，则是像做二维曼哈顿距离最小生成树似的对8个方向做一遍。
即对每个$i$找满足以下条件：
的$j$中$x_j+y_j$最大的$j$。
这个三维偏序由于不存在相关的单调性所以没办法将某两维合并进行单调栈，所以只能老老实实cdq分治。
是的，$O(nlog^2 n)$的cdq分治做8遍，暴力吧。
然后建出来的图缩点，问题就变成了求一个dag上每个点出发能到达多少点。
不可以$O(n)$记搜，因为会重复，不过大样例我会好好地出成记搜能过的数据的。
使用线段树合并判重，因为总边数为$8n$，那么一个节点最多被判重$8$次，总复杂度为$O(8nlogn)=O(nlogn)$。
综上所述，问题可以在$O(nlog^2 n)$的时间与$O(nlogn)$的空间内解决。
难度大概略低于弱省省选，不过码量比较大，提高D2T3的样子。
（因为本地评测时如果开无限栈的话会奇慢无比，所以tarjan写了人工栈）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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
using namespace std;
char _buf[100010],*_op(_buf),*_ed(_buf);
const int N=1e5+1,INF=0x7fffffff,mod=998244853;
LL getint(){
ll _s=0,_f=1;char _ch=gc;
while(_ch<'0'||_ch>'9')_f=(_ch=='-')?-1:1,_ch=gc;
while(_ch>='0'&&_ch<='9')_s=_s*10+_ch-48,_ch=gc;
return _s*_f;
}
int n,h[N],tot;
struct edge{int t,n;}e[N<<3];
V add_edge(int x,int y){if(x>0)e[++tot]=(edge){y,h[x]},h[x]=tot;}
namespace part1{//cdq分治建图
int e1x,e1y,e2x,e2y,cnt;
struct bomb{
ld x,y;int r,id,p1,p2;
V input(int p){x=getint(),y=getint(),r=getint(),id=p;}
V init(){
ld X,Y;
X=(x*e2y-y*e2x)/(e1x*e2y-e2x*e1y);
Y=(x*e1y-y*e1x)/(e2x*e1y-e1x*e2y);
x=X,y=Y;
}
V turn(int opt){
switch(opt){
case 0:y=-y;break;
case 1:x=-x;break;
case 2:swap(x,y);
}
}
}a[N];
V input(){
n=getint(),e1x=getint(),e1y=getint(),e2x=getint(),e2y=getint();
FOR(i,1,n)a[i].input(i),a[i].init();
}
ld val[N<<1];
I find(ld x){
int l=1,r=cnt,mid;
while(mid=l+r>>1,l^r)
if(val[mid+1]<=x)l=mid+1;
else r=mid;
return mid;
}
struct run{
int x,p1,p2,id;
V clean(){x=p1=p2=id=0;}
}b[N],c[N],to[N],t[N<<1];
B cmp(cb x,cb y){return x.y-x.x==y.y-y.x?x.x<y.x:x.y-x.x<y.y-y.x;}
V add(cr x){f_pre if(t[i].id==0||t[i].p2<x.p2)t[i]=x;}
V update(cr x){f_nxt if(to[x.id].id==0||to[x.id].p2<t[i].p2)to[x.id]=t[i];}
V clean(cr x){f_pre t[i].clean();}
V cdq(int l,int r){
if(l==r)return;
int mid=l+r>>1;
cdq(l,mid),cdq(mid+1,r);
int i=l,j=mid+1,cur=l;
while(i<=mid&&j<=r)
if(b[i].x<=b[j].x)add(b[i]),c[cur++]=b[i++];
else update(b[j]),c[cur++]=b[j++];
while(i<=mid)c[cur++]=b[i++];
while(j<=r)update(b[j]),c[cur++]=b[j++];
FOR(k,l,r)clean(b[k]),b[k]=c[k];
}
V work(){
FOR(dir,1,8){
FOR(i,1,n)to[i].clean();
if((dir&3)^1)FOR(i,1,n)a[i].turn(dir&1);
else if(dir^1)FOR(i,1,n)a[i].turn(2);
sort(a+1,a+1+n,cmp),cnt=0;
FOR(i,1,n)val[++cnt]=a[i].x;
sort(val+1,val+1+n),cnt=unique(val+1,val+1+n)-val-1;
FOR(i,1,n)b[i].x=find(a[i].x),b[i].id=a[i].id;cnt=0;
FOR(i,1,n)val[++cnt]=a[i].x+a[i].y+a[i].r;
FOR(i,1,n)val[++cnt]=a[i].x+a[i].y;
sort(val+1,val+1+cnt),cnt=unique(val+1,val+1+cnt)-val-1;
FOR(i,1,n)b[i].p1=find(a[i].x+a[i].y+a[i].r),b[i].p2=find(a[i].x+a[i].y);
cdq(1,n);
FOR(i,1,n)add_edge(to[i].id,i);
}
}
V MAIN(){input(),work();}
}
namespace part2{//tarjan缩点后线段树合并统计答案
int dfn[N],low[N],sta[N],ins[N],co[N],siz[N],rt[N],dp[N];
int up,top,qwq,TAT;
struct run{int u,i,v;}st[N];
V tarjan(int k){
st[++up]=(run){k,-1,0};
run x;
while(up){
start:;
x=st[up--];
if(x.i==-1)x.i=h[x.u],dfn[x.u]=low[x.u]=++qwq,sta[++top]=x.u,ins[x.u]=1;
if(x.v)low[x.u]=min(low[x.u],low[x.v]),x.i=e[x.i].n;
for(;x.v=e[x.i].t,x.i;x.i=e[x.i].n)
if(!dfn[x.v]){
st[++up]=x,st[++up]=(run){x.v,-1,0};
goto start;
}
else if(ins[x.v])low[x.u]=min(low[x.u],dfn[x.v]);
if(dfn[x.u]==low[x.u]){
co[x.u]=++TAT,siz[co[x.u]]++,ins[x.u]=0;
while(sta[top]!=x.u)co[sta[top]]=co[x.u],siz[co[x.u]]++,ins[sta[top]]=0,top--;
top--;
}
}
}
struct bian{
int x,y;
B operator==(const bian&u)const{return this->x==u.x&&this->y==u.y;}
}b[N<<3];
B pp(const bian&x,const bian&y){return x.x==y.x?x.y<y.y:x.x<y.x;}
V clean(){memset(h,0,sizeof(h)),tot=0;}
V maker(){
qwq=unique(b+1,b+1+qwq)-b-1;
FOR(i,1,qwq)add_edge(b[i].x,b[i].y);
}
struct ele{int ls,rs,sum;}t[N<<5];
V update(int p){t[p].sum=t[lc].sum+t[rc].sum;}
I merge(int p,int L,int R,int x){
if(!p||!x)return x|p;
if(L==R)return p;
int mid=L+R>>1;
lc=merge(lson,t[x].ls);
rc=merge(rson,t[x].rs);
update(p);
return p;
}
V dfs(int u){
if(dp[u])return;
REP(i,u,v)dfs(v),rt[u]=merge(rt[u],1,TAT,rt[v]);
dp[u]=t[rt[u]].sum;
}
V insert(int&p,int L,int R,int x){
if(p==0)p=++qwq;
t[p].sum+=siz[x];
if(L==R)return;
int mid=L+R>>1;
if(x>mid)insert(rson,x);
else insert(lson,x);
}
V work(){
FOR(i,1,n)if(!dfn[i])tarjan(i);qwq=0;
FOR(i,1,n)REP(j,i,v)if(co[i]^co[v])b[++qwq]=(bian){co[i],co[v]};
sort(b+1,b+1+qwq,pp),clean(),maker(),qwq=0;
FOR(i,1,TAT)insert(rt[i],1,TAT,i);
FOR(i,1,TAT)if(dp[i]==0)dfs(i);
long long ans=0;
FOR(i,1,n)ans+=1ll*dp[co[i]]*i,ans%=mod;
cout<<ans<<'\n';
}
}
int main(){
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
part1::MAIN();
part2::work();
return 0;
}
不开O2要1.7秒，开O2要1.3秒，所以开了两秒时限。