题意:很简单了,不再赘述。
做法:
首先我们注意到这个代价给的非常奇怪,他可以直接说是除了顶点但是还是要做减法,我们不妨先把这些点和内部的点视为一个点集。
然后我们发现我们并不会求一个随意点的平面上有多少个凸包,所以这个 \(2\) 为底数一定是非常有说法的,很常见的是我们转化为内部的那些点每个都可以选或不选,这样统计答案。
我们发现一个很神奇的事情,这样考虑就等于我们随一个点集,我们直接令他们的凸包围住他就可以了,只要要求随出来的点集不是全部共线即可。
那么答案就是 \(2^n\) 减去共线情况,我们直接枚举两端端点并算出来中间有多少个,假设是 \(x\) 个,那么就减去 \(2^x\) 的贡献。
注意减去单点和空集的答案。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, mod = 998244353;
int x[maxn], y[maxn], n, pw[maxn];
double slope(int i, int j) {if(x[i] == x[j])return 1e9;return (y[j] - y[i]) / (double)(x[j] - x[i]);
}
signed main() {cin >> n;int ans = 1; pw[0] = 1;for (int i = 1; i <= n; i++)cin >> x[i] >> y[i], ans = ans * 2 % mod, pw[i] = ans;for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {int cnt = 0;for (int k = i + 1; k < j; k++)cnt += (slope(i, k) == slope(k, j));ans = (ans - pw[cnt] + mod) % mod;}cout << (ans - n - 1 + mod) % mod << endl;return 0;
}