Description
给定二维平面内\(n\)个点\((n\leq 300)\)，求能组成五角星（不要求正五角星）的五元组个数。
Solution
一道小清新的寄蒜几盒计算几何题，代码不到50行。
一个五元组能组成五角星当且仅当五个点都在凸包上，即存在五条连续的连边，使得极角序递增。
先将边按极角序排序，然后\(dp\)转移。
对于每一条边\(u->v\)，\(dp_{u, v,1}=1\)，转移是\(dp_{S, v, i+1}+=dp_{S,u,i}\)，因为极角序递增，所以所有状态都可以转移。
最后的\(Ans=\sum_{i=1}^{n}dp_{i,i,5}\)。
时间复杂度\(O(n^3)\)
话说snuke睡过头了40min，然后在59min拿了这题的首杀。
Code
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
using namespace std;
struct Vector{int x,y;Vector(int a=0,int b=0):x(a),y(b){}};
Vector operator - (Vector a, Vector b){return Vector(a.x-b.x, a.y-b.y);}
int Cross(Vector A, Vector B) {return A.x*B.y-A.y*B.x;}
bool operator < (Vector A, Vector B) {return Cross(A, B)<0;}
const int N=305;
Vector p[N];
int dp[N][N][6];
vector<pair<Vector, pair<int, int> > > e;
inline int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
signed main()
{
int n=read();
rep(i, 1, n) p[i].x=read(), p[i].y=read();
rep(i, 1, n) rep(j, 1, n) if (i^j)
e.push_back(make_pair(Vector(p[j]-p[i]), make_pair(i, j)));
sort(e.begin(), e.end());
for (auto now: e)
{
int u=now.second.first, v=now.second.second;
dp[u][v][1]++;
rep(i, 1, 5) rep(s, 1, n)
dp[s][v][i+1]+=dp[s][u][i];
}
int ans=0;
rep(i, 1, n) ans+=dp[i][i][5];
printf("%lld\n", ans);
return 0;
}