原题：ConvexScore

原题大意

给出N个点，这N个点可以形成若干个子集S，每个S满足如下条件：S里的所有点正好形成一个凸多边形，每个点都是凸多边形的顶点。
对于任意一个S，n是N个点散布在S的凸包内的个数（包括边界和顶点），S相对应的得分为2^(n-|s|)。求所有得分和，结果模998244353。

算法分析

令Ts = n - |S|,Ts即为集合S的凸包内的点组成的集合（除顶点以外），则题目要求的是合法的Ts子集的种数，Ts最多为2^n，然后减去不合格的集合个数。首先，减去一个空集，再减去n个单点集，然后减去共线的情况（集合全在一条线段上）。

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 200 + 50;
int n;
ll p[maxn];
ll x[maxn], y[maxn];
map<pair<ll, ll>, ll> mp;
void pre(){
    p[0] = 1;
    for(int i = 1; i < maxn; i++){
        p[i] = (p[i-1] * 2) % mod;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    pre();
    while(cin >> n){
        for(int i = 0; i < n; i++)
            cin >> x[i] >> y[i];
        ll ans = p[n] - n - 1;//减去空集和单点集
        ll deltay, deltax, k;
        for(int i = 0; i < n; i++){
            mp.clear();
            for(int j = i+1; j < n; j++){
                deltay = y[j] - y[i];
                deltax = x[j] - x[i];
                k = __gcd(deltay, deltax);
                deltay/=k;
                deltax/=k;
                ++mp[{deltay,deltax}];
                //mp记录共线的点，用pair是防止斜率为0，或者为小数
            }
            for(map<pair<ll, ll>, ll>::iterator iter = mp.begin(); iter != mp.end(); iter++){
                ll tmp = p[iter->second] - 1;//除i点以外共线集的个数，减去只有一个i点的情况
                ans = (ans - tmp + mod) % mod;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}