[??记录]AT3526 [ARC082C] ConvexScore

**题意** ： 给出平面上的点集 $S$。（保证不存在重点） 对于 $T\subseteq S$ ，若 $T$ 中的点可以构成严格凸多边形，记被 $T$ 包在内部（包括边界）的点集为 ${\rm in}(T)$ ，则贡献为 $2^{|{\rm in}(T)|-|T|}$。 求所有 $T$ 的贡献和，答案对 $998244353$ 取模。 $n\leq 200$ ，时限$\texttt{2s}$。 ------------ 这个 $2^{|{\rm in}(T)|-|T|}$ 看起来很刻意，考虑组合意义。 记 $I={\rm in}(T)-T$ ，$2^{|{\rm in}(T)|-|T|}=2^{|I|}$ 即为 $I$ 的子集个数。 问题可以转化为，统计满足 $I'\subseteq {\rm in}(T)-T$ 的二元组 $(T,I')$ 的个数。 可以发现，二元组 $(T,I')$ 和点集 $T+I'$ 是一一对应的，因为根据点集 $T+I'$ 求严格凸包即可得到唯一的 $T$。 于是，问题转化为 ： 求有严格凸包的点集个数。 显然若点集不共线的符合条件，故问题又等价于 ： 求共线点集个数。 单个点必定是“共线”的，单独计算。若有两个点，那么直线是唯一的。 枚举两个点确定直线，然后数有多少个点在直线上，记为 $c$ ，则贡献为 $2^c-c-1$。 暴力枚举，复杂度为 $O(n^3)$ ，可以通过。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 205 using namespace std; const int mod=998244353; struct Point{ int x,y; Point operator - (const Point &B) const {return (Point){x-B.x,y-B.y};} int operator ^ (const Point &B) const {return x*B.y-y*B.x;} }p[MaxN]; bool vis[MaxN][MaxN]; int n,pw2[MaxN],st[MaxN],tn; int main() { scanf("%d",&n); pw2[0]=1; for (int i=1;i<=n;i++)pw2[i]=(pw2[i-1]<<1)%mod; for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); int ans=n+1; for (int u=1;u<=n;u++) for (int v=u+1;v<=n;v++)if (!vis[u][v]){ int tn=2;st[1]=u;st[2]=v; for (int t=v+1;t<=n;t++) if ((p[u]-p[v]^p[t]-p[v])==0) st[++tn]=t; ans=(ans+pw2[tn]-tn-1)%mod; for (int i=1;i<=tn;i++) for (int j=i+1;j<=tn;j++) vis[st[i]][st[j]]=1; } printf("%d",((long long)pw2[n]-ans+mod+mod)%mod); return 0; } ```