Forethought Future Cup - Elimination Round H. Satanic Panic

题目链接

Description

给定$n(n\le 300)$个点，求任选5个点组成凸包的方案数。

Solution

哈又到了一脸懵逼的计算几何啦。
东哥太强啦%%%

将每条双向边拆成两条单向边，然后以起点为坐标原点极角排序。
然后就是dp的活。
设$f[i][j][k]$表示凸包起点为$i$，最后一个点为$j$，$j$是凸包中第$k$个顶点。
当前枚举到$(u,v)$，转移显然$f[i][v][k+1]+=f[i][u][k]$
（因为已经排过序了，所以之前边的极角序都比$(u,v)$，可以直接转移）。
最后答案为${\sum }_{i=1}^{n}f[i][i][5]$。

Code

#include <cstdio>
#include <algorithm>
#include <cmath>using namespace std;#define N 300
#define M 90000#define fo(i, x, y) for(int i = x; i <= y; i ++)#define ll long longvoid read(int &x) {
    char ch = getchar(); x = 0; int bz = 1;while (ch < '0' || ch > '9') {
     if (ch == '-') bz = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - 48, ch = getchar();x *= bz;
}struct EDGE {
     int u, v, x1, y1, x2, y2; double k; } p[M << 1];struct Point {
     int x, y; } a[N + 1];ll f[N + 1][N + 1][6];int n, cnt = 0;void Add(int u, int v, int x1, int y1, int x2, int y2) {
    p[ ++ cnt ] = (EDGE) {
     u, v, x1, y1, x2, y2, atan2(y2 - y1, x2 - x1) };
}void Link(int u, int v, int x1, int y1, int x2, int y2) {
     Add(u, v, x1, y1, x2, y2), Add(v, u, x2, y2, x1, y1); }bool Cmp(EDGE a, EDGE b) {
     return a.k < b.k; }int main() {
    freopen("satanic.in", "r", stdin);freopen("satanic.out", "w", stdout);read(n);fo(i, 1, n) read(a[i].x), read(a[i].y);fo(i, 1, n) fo(j, i + 1, n)Link(i, j, a[i].x, a[i].y, a[j].x, a[j].y);sort(p + 1, p + 1 + cnt, Cmp);fo(i, 1, n) f[i][i][0] = 1;fo(i, 1, cnt)fo(j, 1, n)fo(k, 0, 4) f[j][p[i].v][k + 1] += f[j][p[i].u][k];ll ans = 0;fo(i, 1, n) ans += f[i][i][5];printf("%lld\n", ans);return 0;
}