[arc082E]ConvexScore-[凸包]

Description

传送门

Solution

em又是神仙题。

考虑到目前的一个凸包，顶点点集为S。

现在在它内部或边缘上的点集为T，则贡献为2,设从T中去掉S的点后得到了集合A。则2=2

可知AUS的凸包点集还是S。

好的关键点：A的子集个数为2。怎么样是不是特别棒？

设A'是A的子集，A'US的凸包点集还是为S，这样的A'也恰好有2个，完美。

所以，所有凸包点集为S的点集G，对答案的贡献都为1。

然后注意这里要记得排除共线的情况。假如G中所有点都共线就无法形成凸包啦，减掉这些就OK。PS：空集也要减掉

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

const int mod=;

int n;

ll pw[],ans=;

struct node{int x,y;

}p[];

bool check(node a,node b,node c)

{ return (b.x-a.x)*(c.y-a.y)==(b.y-a.y)*(c.x-a.x);}

void link(int x,int y){x+=y;}

int main()

{

    link(,);

    scanf("%d",&n);

    pw[]=;

    for (int i=;i<=n;i++) pw[i]=(pw[i-]<<)%mod;

    for (int i=;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);

    ans=(pw[n]-n-+mod)%mod;bool _is;int cnt;

    for (int i=;i<n;i++)

        for (int j=i+;j<=n;j++)

        {

            _is=;

            for (int k=;k<i;k++) if (check(p[k],p[i],p[j])) {_is=;break;}

            for (int k=i+;k<j;k++) if (check(p[k],p[i],p[j])) {_is=;break;}

            if (!_is) continue;

            cnt=;

            for (int k=j+;k<=n;k++) if (check(p[k],p[i],p[j])) cnt++;

            ans=(ans-pw[cnt]+cnt++mod)%mod;

        }

    cout<<ans;

}