ConvexScore

题目描述

You are given N points (xi,yi) located on a two-dimensional plane. Consider a subset S of the N points that forms a convex polygon. Here, we say a set of points S forms a convex polygon when there exists a convex polygon with a positive area that has the same set of vertices as S. All the interior angles of the polygon must be strictly less than 180°.

For example, in the figure above, {A,C,E} and {B,D,E} form convex polygons; {A,C,D,E}, {A,B,C,E}, {A,B,C}, {D,E} and {} do not.
For a given set S, let n be the number of the points among the N points that are inside the convex hull of S (including the boundary and vertices). Then, we will define the score of S as 2n−|S|.
Compute the scores of all possible sets S that form convex polygons, and find the sum of all those scores.
However, since the sum can be extremely large, print the sum modulo 998244353.

Constraints
1≤N≤200
0≤xi,yi<104(1≤i≤N)
If i≠j, xi≠xj or yi≠yj.
xi and yi are integers.

输入

The input is given from Standard Input in the following format:
N
x1 y1
x2 y2
:
xN yN

输出

Print the sum of all the scores modulo 998244353.

样例输入

4
0 0
0 1
1 0
1 1

样例输出

5

提示

We have five possible sets as S, four sets that form triangles and one set that forms a square. Each of them has a score of 20=1, so the answer is 5.

题意：
平面上有n(n<=200）个点，对于其中能够构成凸多边形的点集S，计算一个得分score，并输出所有这样能构成凸多边形的点集的得分之和。
score=2^(n-|S|), n: 构成此凸多边形的点数及其内部的点数总和;|S|: 构成此凸多边形的点数。

那么就是要对所有的凸包，求其内部的点数所构成的集合个数。
发现太难求了，总不能枚举所有的凸包啊……
所以我们就从反面来求，求所有点构成的集合个数-不能构成凸包的集合个数
什么样的点不能构成集合？ 单点或共线
所以就枚举所有直线就好了

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=250;
const int p=998244353;
int n;
struct orz{
    int x,y;}a[N];
ll ans;
ll poww(ll x,ll y)
{
    ll ret=1;
    while(y)
    {
        if (y&1) ret=ret*x%p;
        x=x*x%p;
        y>>=1;
    }
    return ret;
}
bool check(int a,int b,int c,int d)
{
    if (a*d==b*c) return 1;
    else return 0;
}
void solve()
{
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            int cnt=0;
            for (int k=j+1;k<=n;k++)
                if (check(a[i].x-a[j].x,a[j].x-a[k].x,a[i].y-a[j].y,a[j].y-a[k].y)) cnt++;
            ans=(ans-poww(2,cnt)+p)%p;
 
        }
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    ans=poww(2,n);
    ans=(ans-1-n+p)%p;
 
    solve();
    printf("%lld
",ans%p);
    return 0;
}