我的【模板】
點分治
#include<bits/stdc++.h>
using namespace std;
const int QAQ=2e5+7,ovo=2e5+7;
int n,m,k,ans,siz[QAQ],ma[QAQ],gen;
vector<int> dian[QAQ],bian[QAQ],cun;
bitset<ovo> vis;
int t[ovo];
int lbd(int x) {return x&(-x);}
void jia(int x,int k) {for(int i=x;i<=(2e5);i+=lbd(i)) t[i]+=k;}
int cha(int x) {if(!x) return 1;int da=0;for(int i=x;i;i-=lbd(i)) da+=t[i];return da+1;}
void getrt(int x,int f,int zong)
{
siz[x]=1,ma[x]=0;
for(int i=0;i<(int)dian[x].size();i++)
{
int v=dian[x][i];
if(vis[v]||v==f) continue;
getrt(v,x,zong),siz[x]+=siz[v];
ma[x]=max(ma[x],siz[v]);
}
ma[x]=max(ma[x],zong-siz[x]);
if(!gen||ma[x]<ma[gen]) gen=x;
}
int cab[QAQ],cnt;
void dfs(int x,int f,int ju)
{
cab[++cnt]=ju;
for(int i=0;i<(int)dian[x].size();i++)
{
int v=dian[x][i];
if(vis[v]||v==f) continue;
dfs(v,x,ju+bian[x][i]);
}
}
void suan(int x)
{
cun.clear();
for(int i=0;i<(int)dian[x].size();i++)
{
int v=dian[x][i];
if(vis[v]) continue;
cnt=0;
dfs(v,x,bian[x][i]);
for(int j=1;j<=cnt;j++) if(k-cab[j]>=0) ans+=cha(k-cab[j]);
for(int j=1;j<=cnt;j++) if(cab[j]<=k) jia(cab[j],1),cun.push_back(cab[j]);
}
for(int i=0;i<(int)cun.size();i++) jia(cun[i],-1);
}
void chuli(int x,int zong)
{
gen=0,getrt(x,0,zong);
vis[gen]=1,suan(gen);
int rt=gen;
for(int i=0;i<(int)dian[rt].size();i++)
{
int v=dian[rt][i];
if(vis[v]) continue;
chuli(v,zong-ma[v]);
}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1,u,v,w;i<n;i++)
cin>>u>>v>>w,dian[u].push_back(v),dian[v].push_back(u),
bian[u].push_back(w),bian[v].push_back(w);
cin>>k;
chuli(1,n);
cout<<ans;
return 0;
}
單調隊列優化四邊形不等式
詩人小 G
#include<bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int QAQ=1e5+7;
const int inf=1e18;
int t,n,l,p,d[QAQ],qz[QAQ],s[QAQ],f[QAQ],cnt;
struct xxx {int l,r,k;} z[QAQ];
ld dp[QAQ];
ld ksm(ld x,int k)
{
ld da=1;
for(;k;k>>=1,x=x*x) if(k&1) da=da*x;
return da;
}
ld zhi(int i,int j) {return dp[i]+ksm(abs(qz[j]-qz[i]-1-l),p);}
int erfen(int i,int j)
{
int l=z[i].l,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(zhi(z[i].k,mid)>=zhi(j,mid)) r=mid-1;
else l=mid+1;
}
return r;
}
int zb,yb;
void work()
{
zb=1,yb=0;
z[++yb]={1,n,0};
for(int i=1;i<=n;i++)
{
while(zb<=yb&&z[zb].r<i) zb++;
if(zb<=yb) z[zb].l=i;
dp[i]=zhi(z[zb].k,i);
f[i]=z[zb].k;
while(zb<=yb&&zhi(z[yb].k,z[yb].l)>=zhi(i,z[yb].l)) yb--;
if(zb>yb) yb++,z[yb]={i,n,i};
else if(zhi(z[yb].k,n)>zhi(i,n))
z[yb].r=erfen(yb,i),yb++,z[yb]={z[yb-1].r+1,n,i};
}
}
string a[QAQ];
signed main()
{
cin>>t;
for(int i1=1;i1<=t;i1++)
{
cin>>n>>l>>p;
for(int i=1;i<=n;i++)
{
cin>>a[i];
d[i]=a[i].size();
qz[i]=qz[i-1]+d[i]+1;
}
work();
if(dp[n]<=inf)
{
cout<<(int)dp[n]<<"\n";
cnt=0;
for(int i=n;i>=1;) s[++cnt]=f[i],i=f[i];
s[0]=n;
for(int i=cnt-1;i>=0;i--)
{
for(int j=s[i+1]+1;j<=s[i]-1;j++) cout<<a[j]<<" ";
cout<<a[s[i]]<<"\n";
}
}
else puts("Too hard to arrange");
puts("--------------------");
}
return 0;
}
tarjan
縮點（有向圖）
void tajian(int x)
{
dfn[x]=++hao;
low[x]=dfn[x];
zai[x]=1;
zhan[++top]=x;
for(int i=head[x];i;i=e[i].nex)
{
int v=e[i].to;
if(!dfn[v]) tajian(v),low[x]=min(low[x],low[v]);
else if(zai[v]) low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
++ke;
while(zhan[top]!=x)
{
kuai[zhan[top]]=ke;
f[ke]+=a[zhan[top]];
zai[zhan[top]]=0;
top--;
}
f[ke]+=a[zhan[top]];
dp[ke]=f[ke];
kuai[zhan[top]]=ke;
zai[zhan[top]]=0;
top--;
}
}
割點（無向邊）
void tajian(int u)
{
int ji=0;
dfn[u]=++cnt;low[u]=cnt;
for(int i=head[u],v;i;i=xia[i])
{
if(vis[i^1]) continue; vis[i]=1;
v=to[i];
if(!dfn[v])
{
tajian(v),low[u]=min(low[u],low[v]);
if(u!=gen&&low[v]>=dfn[u]) ok[u]=1;
ji++;
}
else low[u]=min(low[u],dfn[v]);
}
if(u==gen&&ji>1) ok[u]=1;
}
點雙（無向邊）
void tajian(int u)
{
int son=0;
dfn[u]=++cnt;low[u]=cnt;
zhan[++top]=u;
for(int i=head[u],v;i;i=xia[i])
{
if(vis[i^1]) continue; vis[i]=1;
v=to[i];
if(!dfn[v])
{
son++,tajian(v),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
std::vector<int> x;
x.push_back(u);
while(zhan[top]!=v) x.push_back(zhan[top--]);
x.push_back(zhan[top--]);
ans.push_back(x);
}
}
else low[u]=min(low[u],dfn[v]);
}
if(gen==u&&!son)
{
vector<int> x;
x.push_back(u);
ans.push_back(x);
}
}
邊雙（無向邊）
void tajian(int u)
{
dfn[u]=++cnt;low[u]=cnt;
zhan[++top]=u;
for(int i=head[u],v;i;i=xia[i])
{
if(vis[i^1]) continue; vis[i]=1;
v=to[i];
if(!dfn[v]) tajian(v),low[u]=min(low[u],low[v]);
else low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
vector<int> x=kong;
while(zhan[top]!=u&&top) x.push_back(zhan[top--]);
x.push_back(zhan[top--]);
ans.push_back(x);
}
}
AC 自動機
#include<bits/stdc++.h>
using namespace std;
const int QAQ=210000;
string t[QAQ],s;
int n,xu[QAQ],ch[QAQ][28],cnt,zhi[QAQ*10],ru[QAQ],ans[QAQ];
vector<int> id[QAQ];
void jia(string s,int lai)
{
int p=0;
for(int i=0;i<(int)s.size();i++)
{
if(!ch[p][s[i]-'a'+1]) ch[p][s[i]-'a'+1]=++cnt;
p=ch[p][s[i]-'a'+1];
}
id[p].push_back(lai);
}
void pao(string s)
{
for(int i=0,p=0;i<(int)s.size();i++) p=ch[p][s[i]-'a'+1],zhi[p]++;
}
queue<int> dui;
vector<int> dian[QAQ];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>t[i],jia(t[i],i);
for(int i=1;i<=26;i++) if(ch[0][i]) dui.push(ch[0][i]),xu[ch[0][i]]=0;
while(!dui.empty())
{
int x=dui.front();dui.pop();
for(int i=1;i<=26;i++)
{
if(ch[x][i]) xu[ch[x][i]]=ch[xu[x]][i],ru[ch[xu[x]][i]]++,dui.push(ch[x][i]);
else ch[x][i]=ch[xu[x]][i];
}
}
cin>>s,pao(s);
for(int i=0;i<=cnt;i++) if(ru[i]==0) dui.push(i);
while(!dui.empty())
{
int x=dui.front();dui.pop();
zhi[xu[x]]+=zhi[x];
ru[xu[x]]--;
if(ru[xu[x]]==0) dui.push(xu[x]);
}
for(int i=1;i<=cnt;i++) for(int j=0;j<(int)id[i].size();j++) ans[id[i][j]]=zhi[i];
for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
return 0;
}
SPFA
bool vis[110000];
int n,m,s,dis[110000];
vector<int> dian[110000],bian[110000];
void sp(int s)
{
queue<int> dui;
dis[s]=0;
dui.push(s);
vis[s]=1;
while(!dui.empty())
{
int x=dui.front();dui.pop();
vis[x]=0;
int chang=dian[x].size();
for(int i=0;i<chang;i++)
{
int v=dian[x][i];
if(dis[v]>dis[x]+bian[x][i])
{
dis[v]=dis[x]+bian[x][i];
if(!vis[x]) dui.push(v),vis[v]=1;
}
}
}
}
匈牙利算法
bool vis[51000];
int da,n,m,e,bian[51000];
vector<int> dian[11000];
bool dfs(int x)
{
int chang=dian[x].size();
for(int i=0;i<chang;i++)
{
int v=dian[x][i];
if(vis[v]) continue;
else vis[v]=1;
if(!bian[v]||dfs(bian[v])) {bian[v]=x;return 1;}
}
return 0;
}
int main()
{
cin>>n>>m>>e;
for(int i=1,u,v;i<=e;i++) cin>>u>>v,dian[u].push_back(v);
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) da++;
}
cout<<da;
return 0;
}
exgcd
void exgcd(ll a,ll b)
{
if(b==0) {x=1,y=0;return;}
exgcd(b,a%b);
long long cab=x;
x=y;
y=cab-a/b*y;
}//ax+by=gcd(a,b)
數位 DP
int len,f[21][21][21][2][2][2][2],w[21];
int dfs(int pos,int ss,int s,bool pan,bool si,bool ba,bool g)
{
if(si&&ba) return 0;
if(pos==0) return pan;
if(f[pos][ss][s][pan][si][ba][g]!=-1) return f[pos][ss][s][pan][si][ba][g];
int ans=0;
int lim=(g?w[pos]:9);
for(int i=0;i<=lim;i++)
{
ans+=dfs(pos-1,s,i,pan||(ss==s&&s==i),(si||i==4),(ba||i==8),g&&(i==lim));
}
f[pos][ss][s][pan][si][ba][g]=ans;
return ans;
}
int suan(int x)
{
memset(f,-1,sizeof(f));
len=0;
while(x)
{
w[++len]=x%10;
x/=10;
}
if(len<11) return 0;
int ans=0;
for(int i=1;i<=w[len];i++)
ans+=dfs(len-1,0,i,0,i==4,i==8,i==w[len]);
return ans;
}
signed main()
{
int l,r;
cin>>l>>r;
cout<<suan(r)-suan(l-1);
return 0;
}
全源最短路
我們新建一個虛擬節點（在這里我們就設它的編號為 0 ）。從這個點向其他所有點連一條邊權為 0 的邊。
接下來用 Bellman-Ford 算法求出從 0 號點到其他所有點的最短路，記為 h[i] 。
跑一邊 SPFA 將所有邊的邊權設置為 \(w+h[u]?h[v]\)，然后跑 dij。
后綴自動機
例題題意小補充：t 為 1 表示不同位置的相同子串算作多個。
struct xxx
{
int tr[QAQ][31],fa[QAQ],cnt,last;
ll len[QAQ],ci[QAQ],f[QAQ];
void init() {cnt=1,last=1;}
void add(int x)
{
int p=last,np=++cnt,q,nq;last=np;
len[np]=len[p]+1,ci[np]=f[np]=1;
for(;p&&!tr[p][x];p=fa[p]) tr[p][x]=np;
if(!p) fa[np]=1;
else
{
q=tr[p][x];
if(len[q]==len[p]+1) fa[np]=q;
else
{
nq=++cnt;
for(int i=0;i<26;i++) tr[nq][i]=tr[q][i];
fa[nq]=fa[q],len[nq]=len[p]+1,fa[q]=fa[np]=nq;
for(;p&&tr[p][x]==q;p=fa[p]) tr[p][x]=nq;
}
}
}
void dfs1(int x)
{
for(int i=0;i<(int)dian[x].size();i++) dfs1(dian[x][i]),ci[x]+=ci[dian[x][i]];
f[x]=ci[x];
}
ll dfs2(int x)
{
if(vis[x]) return f[x];vis[x]=1;
for(int i=0;i<26;i++) if(tr[x][i]!=0) f[x]+=dfs2(tr[x][i]);
return f[x];
}
void cha(ll x,ll k)
{
if(k<=ci[x]) return ;///////////////////////
k-=ci[x];
for(int i=0;i<26;i++)
{
ll v=tr[x][i];
if(k>f[v]) k-=f[v];
else return cout<<(char)('a'+i),cha(v,k),void();
}
}
void gowork()
{
init();
for(int i=0;i<(int)s.size();i++) add(s[i]-'a');
cin>>t>>k;
for(int i=1;i<=cnt;i++) dian[fa[i]].push_back(i);
if(t) dfs1(1);
else for(int i=1;i<=cnt;i++) f[i]=ci[i]=1;
f[1]=ci[1]=0,dfs2(1);
if(k>f[1]) return puts("-1"),void();
cha(1,k);
}
} qwp;
dinic
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int QAQ=1e4+7,inf=(2e15+7);
int n,m,s,t,cnt=1,head[510000],kai[510000];
struct xxx {int to,nex,w;} e[QAQ];
void add(int x,int y,int c)
{
e[++cnt].to=y;
e[cnt].w=c;
e[cnt].nex=head[x];
head[x]=cnt;
e[++cnt].to=x;
e[cnt].w=0;
e[cnt].nex=head[y];
head[y]=cnt;
}
int dis[510000],da;
bool bfs()
{
for(int i=1;i<=n;i++) dis[i]=inf;
queue<int> dui;
dui.push(s);dis[s]=0;
kai[s]=head[s];
while(!dui.empty())
{
int x=dui.front();dui.pop();
for(int i=head[x];i;i=e[i].nex)
{
int v=e[i].to;
if(e[i].w>0&&dis[v]==inf)
{
dui.push(v),kai[v]=head[v],dis[v]=dis[x]+1;
}
}
}
if(dis[t]!=inf) return 1;
return 0;
}
int dfs(int x,int xian)
{
if(x==t) return xian;
int k,liu=0;
for(int i=kai[x];i&&xian>0;i=e[i].nex)
{
kai[x]=i;
int v=e[i].to;
if(e[i].w>0&&(dis[v]==dis[x]+1))
{
k=dfs(v,min(xian,e[i].w));
if(k==0) dis[v]=inf;
e[i].w-=k,e[i^1].w+=k;
liu+=k,xian-=k;
}
}
return liu;
}
signed main()
{
cin>>n>>m>>s>>t;
for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,add(u,v,w);
while(bfs()) da+=dfs(s,inf);
cout<<da;
return 0;
}
費用流（EA）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int QAQ=3e5+7,inf=2e13;
int n,m,s,t,head[QAQ],cnt=1;
struct xxx {int nex,to,w,c;} e[QAQ];
void add(int x,int y,int w,int c)
{
e[++cnt]={head[x],y,w,c};
head[x]=cnt;
e[++cnt]={head[y],x,0,-c};
head[y]=cnt;
}
int da1,da2,dis[QAQ],f[QAQ],from[QAQ];
queue<int> dui;
bitset<QAQ> vis;
bool spfa()
{
while(!dui.empty()) dui.pop();
for(int i=0;i<=n*2;i++) f[i]=inf,vis[i]=0;
dui.push(s);
f[s]=0;
vis[s]=1;
dis[s]=inf;
while(!dui.empty())
{
int x=dui.front();dui.pop();
vis[x]=0;
for(int i=head[x];i;i=e[i].nex)
{
int v=e[i].to,w=e[i].w,c=e[i].c;
if(f[v]>f[x]+c&&w>0)
{
f[v]=f[x]+c;
dis[v]=min(dis[x],w);
from[v]=i;
if(vis[v]) continue;
dui.push(v);
vis[v]=1;
}
}
}
if(f[t]<1e10) return 1;
return 0;
}
void geng()
{
int x=t,p;
while(x!=s) p=from[x],e[p].w-=dis[t],e[p^1].w+=dis[t],da2+=dis[t]*e[p].c,x=e[p^1].to;
da1+=dis[t];
}
signed main()
{
cin>>n>>m>>s>>t;
for(int i=1,u,v,w,c;i<=m;i++)
{
cin>>u>>v>>w>>c;
add(u,v,w,c);
}
while(spfa()) geng();
cout<<da1<<" "<<da2;
return 0;
}
模擬退火
#include<bits/stdc++.h>
using namespace std;
double kai=10000,eps=1,jiang=0.92,fw;//fw 記得賦值
mt19937 rd(time(0));
#define bu t*(rd()%(2*(int)fw)*1.0-fw)
#define gl 1.0*rand()/RAND_MAX
int ans,sx;//題目要求時開 double
int cha(int x)
{
/*
*/
return ans;
}
signed main()
{
srand(20090918);
sx=;//
fw=;//
ans=cha(sx);
while (1.0*clock()/CLOCKS_PER_SEC<0.9)
{
int nw=ans,x=sx;
for(double t=kai;t>eps;t*=jiang)
{
int o1=x+bu,k;
while(o1∈[?,?]) o1=x+bu;
k=cha(o1);
if(k>ans) ans=k,sx=o1;
if(k>nw||exp((k-nw)/t)>gl) x=o1;
}
}
cout<<ans;
return 0;
}
模擬退火不能無腦退火，要結合性質。
- 構造好初始解
- 猜想答案特性
- 選擇更牛的隨機下一步的方式
- 優化 calc
- 調參。
答案數組最好開 double，不開的話一定要記得在 \(△d/t\) 時加上 1.0* 不然你就會完了！
下面是數學的領域
atan2(△y,△x) ：極角
acos(-1)：π
cos()、sin()：。
__builtin_popcount(x)、__builtin_popcountll(x)：1 的個數
兩直線交點
設兩直線方程分別為：
\(l_1=P+t\)v
\(l_2=Q+t\)w
\(t=[(P?Q)×\)w\(]/(\)w\(×\)v\()\)。
三點定圓
void ding(xxx o1,xxx o2,xxx o3)
{
double
a1=o2.x-o1.x,a2=o3.x-o1.x,
b1=o2.y-o1.y,b2=o3.y-o1.y,
c1=(o2.x*o2.x-o1.x*o1.x+o2.y*o2.y-o1.y*o1.y)/2,
c2=(o3.x*o3.x-o1.x*o1.x+o3.y*o3.y-o1.y*o1.y)/2;
o={(b2*c1-b1*c2)/(b2*a1-b1*a2),(a2*c1-a1*c2)/(a2*b1-a1*b2)};
r=dis(o,o1)+eps;
}
叉積求面積
\(S_{△}=\frac{a×b}{2}\)
切比雪夫距離與曼哈頓距離
曼哈頓 \((x,y) = (x+y,x-y)\) 的切比雪夫
切比雪夫 \((x,y) = ((x+y)/2,(x-y)/2)\) 的曼哈頓
累加公式
平方：\(n(n+1)(2n+1)/6\)
立方：\([n(n+1)/2]^2\)
證明是數形結合旋轉三角形/體。
插板法
把 n 個蘋果分給 m 個人：
\(C_{m+n-1}^{n-1}\)
log
log(a)：以 e 為底
log2(a)：以 2 為底
log(a)/log(b)：以 b 為底
__lg()：以 2 為底，int 類型
1. 旋轉坐標系
公式
- 繞原點旋轉?：
逆時針旋轉θ角度時：
\(x′=xcos?θ?ysin?θ\)
\(y′=xsin?θ+ycos?θ\)
逆時針旋轉 θ 度矩陣：
| cos(θ) | sin(θ) |
|---|---|
| -sin(θ) | cos(θ) |
- 繞任意點 \((a,b)\) 旋轉?：
分三步實現：平移坐標系使旋轉中心到原點→應用繞原點旋轉公式→反向平移。公式為：
\(x′=(x?a)cos?θ?(y?b)sin?θ+a\)
\(y′=(x?a)sin?θ+(y?b)cos?θ+b\)
二維凸包
先找 \(y\) 最小的那個點，用 atan2(△y,△x) 極角排序其余點，然后維護棧，如果棧頂兩個點的直線與當前點與棧頂點的直線叉積 \(<0\)，那么彈棧，最后再插入一下最開始那個點就是凸包了。
\(a×b=x_a×y_b-y_a×x_b\)
\(a×b<0\) 則 b 是 a 順時針旋轉。
\(a×b>0\) 則 b 是 a 逆時針旋轉。
細節：
cmp1 若 y 等則按 x 排。
cmp2 若 val 等則按 y 排。
怎么排無所謂。
數論分塊
把 \(\%\) 拆為下取整除法。
\(l\) 所在塊的右端點為 \(k/(k/l)\)。
\(l=r+1\)
6. 半平面交
小言
逆轉叉積正。
一個直線我們只取它左邊。
流程
極角排序所有直線，如果極角相同優先靠左的直線。
存兩個隊列——交點隊列和直線隊列，注意交點隊列在運算時總是比直線隊列短 \(1\)
遍歷所有直線，如果兩個直線極角一樣（差 eps）那么不重復計算，在交點隊列彈掉所有在當前直線右邊的點。
把當前直線加入直線隊列并在交點隊列里加上其與直線隊列上一個直線的交點。
最后再用直線隊列的尾消一下交點隊列的頭
再拿新直線隊列的頭消一下交點隊列的尾
如果最后直線隊列長度小于 \(3\)，那么無解。（其實要特判一下只有一點直線的情況，我們可以直接在開始插入四個超級直線解決）
還要記得把開頭的直線和末尾的直線的交點加進去，最后所有交點組成的凸包是半平面交。
求面積就選擇點 \(1\)，從它開始分割很多三角形，用叉積除二求面積即可。
#include<bits/stdc++.h>
using namespace std;
const int QAQ=1010;
const double eps=1e-9,inf=1000;
int n,cnt,ccx;
struct dian {double x,y;} d[QAQ],jd[QAQ],ans[QAQ];
struct bian {dian x,y;double s;} l[QAQ],dui[QAQ];
double cha(dian a,dian b) {return a.x*b.y-a.y*b.x;}
dian operator + (dian a,dian b) {return {a.x+b.x,a.y+b.y};}
dian operator * (dian a,double b) {return {a.x*b,a.y*b};}
dian xl(dian a,dian b) {return {b.x-a.x,b.y-a.y};}
bool you(dian p,bian s) {return cha(xl(s.x,p),xl(s.x,s.y))>0;}
bool cmp1(bian a,bian b) {return (a.s==b.s)?you(b.x,a):a.s<b.s;}
dian jiao(bian a,bian b)
{
dian o1=xl(a.x,a.y),o2=xl(b.x,b.y),o3=xl(b.x,a.x);
double cab=cha(o3,o2)/cha(o2,o1);
return a.x+o1*cab;
}
void work()
{
for(int i=1;i<=cnt;i++)
l[i].s=atan2(l[i].y.y-l[i].x.y,l[i].y.x-l[i].x.x);
sort(l+1,l+cnt+1,cmp1);
int zb=1,yb=0;
dui[++yb]=l[1];
for(int i=2;i<=cnt;i++)
{
if(fabs(l[i].s-l[i-1].s)<eps) continue;
while(zb<yb&&you(jd[yb-1],l[i])) yb--;
while(zb<yb&&you(jd[zb],l[i])) zb++;
dui[++yb]=l[i];
if(zb<yb) jd[yb-1]=jiao(dui[yb],dui[yb-1]);
}
while(zb<yb&&you(jd[yb-1],dui[zb])) yb--;
while(zb<yb&&you(jd[zb],dui[yb])) zb++;
if(yb-zb+1<=2) return ;
jd[yb]=jiao(dui[zb],dui[yb]);
for(int i=zb;i<=yb;i++) ans[++ccx]=jd[i];
}
signed main()
{
cin>>n;
for(int i=1,m;i<=n;i++)
{
cin>>m;
for(int j=1;j<=m;j++) cin>>d[j].x>>d[j].y;
for(int j=1;j<m;j++) l[++cnt]={d[j],d[j+1]};
l[++cnt]={d[m],d[1]};
}
dian a={-inf,inf},b={inf,inf},c={-inf,-inf},d={inf,-inf};
l[++cnt]={a,c},l[++cnt]={c,d},l[++cnt]={d,b},l[++cnt]={b,a};
work();
double da=0;
for(int i=2;i<ccx;i++) da+=cha(xl(ans[1],ans[i]),xl(ans[1],ans[i+1]));
printf("%.3f",da/2);
return 0;
}
浙公網安備 33010602011771號