题解：AT_arc082_c [ARC082E] ConvexScore
Drink_Assam
·
·
题解
列式子的题解更易懂！
题意
设 k(S) 为凸包 S 内部或边上的点数（不含顶点），即
k(S)=
\big |\small\{P|P\notin S\wedge P\text{被}S\text{包住}\}\big |
给定 N 个点，求
\sum\limits_S 2^{k(S)}
考虑推式子。
\begin{aligned}
{}&\sum\limits_S 2^{k(S)}\\
=&\sum\limits_S 2^{\big |\small\{P|P\notin S\wedge P\text{被}S\text{包住}\}\big |}\\
=&\sum\limits_S\sum\limits_{T}[T\subseteq\{P|P\notin S\wedge P\text{被}S\text{包住}\}]\\
=&\sum\limits_S\sum\limits_{T}[T\cap S=\emptyset\wedge T\text{被S包住}]\\
=&\sum\limits_S\sum\limits_{T}[T\text{被S包住}]\sum\limits_{W}[T=∁_W S]\\
=&\sum\limits_{W}\sum\limits_{S\subseteq W}[S\text{包住了}∁_W S]\\
=&\sum\limits_{W}\sum\limits_{S\subseteq W}[S\text{是}W\text{内最大的凸包}]\\
=&\sum\limits_{W}[W\text{中存在凸包}]\\
=&2^N-\sum\limits_{W}[W\text{中不存在凸包}]\\
=&2^N-\sum\limits_{W}[W中所有点共线]\\
=&2^N-\sum\limits_{\text{直线}l}2^{l\text{覆盖的点数}}\\
\end{aligned}
枚举直线即可。