太菜了完全不会计算几何，开新坑（一定不会咕咕咕
建立平面直角坐标系。
点 $P$ ，用点对 $(x,y)$ 表示 。
向量 $\vec{a}$ ，同样用点对 $(x,y)$ 表示。
向量 $\overrightarrow{AB}\ =\ (x_B-x_A,y_B-y_A)$ 。
向量模长 $|\vec{a}|=\sqrt{x^2+y^2}$ 。
向量点乘（点积），$\vec{a}\cdot \vec{b}=|\vec{a}||\vec{b}|\cos \alpha$ ，其中 $\alpha$ 为夹角 。
点积还可以表示为 $x_ax_b+y_ay_b$ 。
向量夹角 $=\arccos\dfrac{\vec{a}\cdot \vec{b}}{|\vec{a}||\vec{b}|}$ 。
向量叉乘（叉积），$\vec{a}\times \vec{b}=|\vec{a}||\vec{b}|\sin \alpha$ ，其中 $\alpha$ 为夹角 。
注意叉乘**没有交换律**。
叉乘的结果还是一个向量，但为方便只保留模长。
叉乘还可以表示为 $x_ay_b-x_by_a$ 。
$S_{\triangle abc}=\overrightarrow{ab}\times \overrightarrow{ac}$ 。注意这是有向面积，一般取绝对值。
判断点 $O$ 是否在 $\triangle ABC$ 内。
方法 $1$ ，运用点乘，判断 $\angle AOB+\angle BOC+\angle AOC$ 是否等于 $2\pi$ 。
方法 $2$ ，运用叉乘，判断 $S_{\triangle AOB}+S_{\triangle AOC}+S_{\triangle BOC}$ 是否等于 $S_{\triangle ABC}$ 。
凸包：Graham算法
对于所有点按 $x$ 从小到大排序，从第一个点开始。
开栈维护当前凸壳，加入最后一个点时将栈顶不合法元素弹出即可。
注意上凸壳和下凸壳要分开维护。
显然凸包的一个三角剖分可以同时求出。
------------------------------
题目大意：给定 $N$ 个整点，求有多少个子集的凸包面积为整数。
考虑固定凸包，那么凸包内的节点可以随便选与不选。
那么如何计算凸包个数，我们可以固定最左端点 $s$ ，然后模拟 Graham 算法。
维护上凸壳 $f_{i,j,0/1}$ 表示 上凸壳的最后两个点为 $i,j$ ，当前面积$\times 2$ 后为奇数还是偶数。
初始化 $f_{s,i,0}=1$ 。
转移枚举 $i,j,k$ ，如果$slope_{i,j}>slope_{j,k}$，则可以 $f_{i,j}\to f_{j,k}$ 。
下凸包同理。
最后合并上下凸包即为答案。
时间复杂度 $\rm O(N^4)$ 。
```cpp
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 85
#define P 1000000007
using namespace std;
int n;
struct node{
int x,y;
node(int X=0,int Y=0){x=X,y=Y;}
bool operator<(const node o)const{
if(x!=o.x)return x<o.x;
return y<o.y;
}
}p[N];
node vec(node x,node y){return node(y.x-x.x,y.y-x.y);}
int mul(node x,node y){return abs(x.x*y.y-y.x*x.y);}
int s(node x,node y,node z){return mul(vec(x,y),vec(x,z));}
bool ck(node x,node y,node z,node k){return s(x,y,z)==s(x,y,k)+s(x,z,k)+s(y,z,k);}
int cnt[N][N][N],op[N][N][N],f[N][N][2],g[N][N][2],pw[N];
double slope(node x,node y){
if(x.x==y.x)return 1e9;
x=vec(x,y);
return 1.00*x.y/x.x;
}
int main(){
scanf("%d",&n);
pw[0]=1;rep(i,1,n)pw[i]=(pw[i-1]<<1)%P;
rep(i,1,n)scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+n+1);
rep(i,1,n)rep(j,1,n)rep(k,1,n)if(i!=j&&j!=k&&i!=k){
rep(w,1,n)if(i!=w&&j!=w&&k!=w)cnt[i][j][k]+=ck(p[i],p[j],p[k],p[w]);
op[i][j][k]=s(p[i],p[j],p[k])&1;
}
int ans=0;
rep(i,1,n){
memset(f,0,sizeof(f));memset(g,0,sizeof(g));
rep(j,i+1,n)f[i][j][0]=g[i][j][0]=1;
rep(c,i+2,n)rep(b,i+1,c-1)rep(a,i,b-1)if(slope(p[a],p[b])>slope(p[b],p[c]))
f[b][c][(0+op[i][b][c])&1]+=1LL*f[a][b][0]*pw[cnt[i][b][c]]%P,
f[b][c][(1+op[i][b][c])&1]+=1LL*f[a][b][1]*pw[cnt[i][b][c]]%P,
f[b][c][0]%=P,f[b][c][1]%=P;
rep(c,i+2,n)rep(b,i+1,c-1)rep(a,i,b-1)if(slope(p[a],p[b])<slope(p[b],p[c]))
g[b][c][(0+op[i][b][c])&1]+=1LL*g[a][b][0]*pw[cnt[i][b][c]]%P,
g[b][c][(1+op[i][b][c])&1]+=1LL*g[a][b][1]*pw[cnt[i][b][c]]%P,
g[b][c][0]%=P,g[b][c][1]%=P;
rep(j,i+1,n)rep(k,j+1,n)ans+=(f[j][k][0]+g[j][k][0])%P,ans%=P;
rep(k,i+2,n){
int L=0,R=0;
rep(j,i+1,k-1)L+=f[j][k][0],R+=g[j][k][0],L%=P,R%=P;
ans+=1LL*L*R%P;L=R=0;ans%=P;
rep(j,i+1,k-1)L+=f[j][k][1],R+=g[j][k][1],L%=P,R%=P;
ans+=1LL*L*R%P;ans%=P;
}
}
printf("%d\n",ans);
return 0;
}
```
计算几何入门 &【题解】F - Integer Convex Hull
原文：https://www.cnblogs.com/SharpnessV/p/14855400.html