【牛客挑战赛38：E】七星阵（极角排序+dp+思维）

传送门

• 题目：
  
  input：

9 3
-1997 94
-1591 -1211
-439 -1951
917 -1777
1845 -771
1909 594
1080 1682
-253 1983
-1469 1356
1000 0
-499 866
-500 -866

output:

36

样例对应的图：

• 思路：
  红点组成七边形，可以从一个顶点将这七边形划分为6个三角形，每个三角形内的蓝点数之和=3即满足七星阵的要求。
  根绝这个思路，首先要求出由n个红点构成的所有三角形内的蓝点数，由于题目保证不存在三点共线，所以蓝点不会出现在三角形的边（由两个红点连接而成）和顶点上，只会出现在三角形的内部。
  • 将n个红点两两相连，构成 $n\ast (n-1)$n∗(n−1)条有向边，存入pair，first->second
  • 将这些有向边按照极角排序，为了避免可能存在精度误差，使用叉积而不是atan2进行排序
  • 对于指向朝上的边，统计其右侧有多少个蓝点（满足蓝点的y值在边的y值区间内，负值）；对于指向朝下的边，统计其左侧有多少个蓝点（满足蓝点的y值在边的y值区间内，正值），那么对于 $A,B,C$A,B,C三点构成的三角形，其内的蓝点数为： $abs\left(cnt\right[A\left]\right[B]+cnt[B\left]\right[C]+cnt[C\left]\right[A\left]\right)$abs(cnt[A][B]+cnt[B][C]+cnt[C][A]), $cnt\left[i\right]\left[j\right]$cnt[i][j]表示上述统计的值：
    
    
    枚举七边形的起点（不将其计为七边形的1号点，把它当做终点七号点），按照之前极角排序后的边逆时针找从该起点开始能够组成的七星阵数目。
    $dp\left[i\right]\left[j\right]\left[k\right]$dp[i][j][k]表示当前处理的红点编号为i，它在七边形的编号为j（从起点开始逆时针方向数），且该七边形的1-j号点内包含k个蓝点的方法数。
    枚举n个起点，每次将dp清空，dp[i][0][0]=1,枚举j和k，转移方程：
    ${\displaystyle dp\left[v\right]\left[j\right]\left[k\right]=\sum _{1\le j\le 7,0\le k\le 3}dp\left[u\right][j-1]\left[k\right]}$dp[v][j][k]=1≤j≤7,0≤k≤3∑​dp[u][j−1][k] 存在有向边 $u\Rightarrow v$u⇒v
    并且从当前 $i,u,v$i,u,v构成的三角形内选择一定数目的蓝点x(总数目为num)，使得和之前选定的蓝点数目k之和不超过3
    ${\displaystyle dp\left[v\right]\left[j\right][x+k]=\sum _{1\le j\le 7,x+k\le 3,0\le k\le 3}dp\left[u\right][j-1]\left]\right[k]\ast C_{num}^x}$dp[v][j][x+k]=1≤j≤7,x+k≤3,0≤k≤3∑​dp[u][j−1]][k]∗Cnumx​
    ${\displaystyle ans=\sum _{i=1}^{n}dp\left[i\right]\left[7\right]\left[3\right]}$ans=i=1∑n​dp[i][7][3]
• ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 160;
const ll mod = 998244353;
struct Point//点或向量
{
    double x, y;
    Point(double x = 0, double y = 0) :x(x), y(y) {}
};
typedef Point Vector;
Vector operator - (Vector a, Vector b)//向量减法
{
    return Vector(a.x - b.x, a.y - b.y);
}
double Cross(Vector a, Vector b)//外积
{
    return a.x * b.y - a.y * b.x;
}
double Angle(Vector a)//极角，(-pi，pi]
{
    return atan2(a.y, a.x);
}
int n, m;
Point r[maxn], b[1010];
vector<pii> link;
int cnt[maxn][maxn];
ll dp[maxn][10][5];
bool cmp(pii A, pii B)
{
    return Cross(r[A.second]-r[A.first], r[B.second]-r[B.first]) > 0;//first->second的向量
    //return Angle(r[A.second]-r[A.first])<Angle(r[B.second]-r[B.first]);
}
ll add(ll a, ll b) {return (a%mod+b%mod)%mod;}
ll mul(ll a, ll b) {return a%mod*(b%mod)%mod;}
 
 
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lf %lf", &r[i].x, &r[i].y);
    for(int i = 1; i <= m; i++) scanf("%lf %lf", &b[i].x, &b[i].y);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i!=j) link.push_back({i, j});//i->j的有向边
    sort(link.begin(), link.end(), cmp);//极角排序
    for(auto e:link)
    {
        Point p1 = r[e.first], p2 = r[e.second];
        for(int i = 1; i <= m; i++)
        {
            Point p3 = b[i];
            if(p3.y>=max(p1.y, p2.y) || p3.y<=min(p1.y, p2.y)) continue;
            //不统计p1.y=p2.y
            if(p1.y>p2.y && Cross(p3-p1, p2-p1)<0) cnt[e.first][e.second]++;//first->second左侧有点
            if(p1.y<p2.y && Cross(p3-p1, p2-p1)>0) cnt[e.first][e.second]--;//first->second右侧有点
        }
    }
    ll ans = 0;
    /*for(auto e:link) { printf("%d %d %d\n", e.first, e.second, cnt[e.first][e.second]); }*/
    for(int i = 1; i <= n; i++)//枚举外层凸包的起点，逆时针统计方法数
    {
        memset(dp, 0, sizeof dp);
        dp[i][0][0] = 1;
        for(auto e:link)
        {
            int u = e.first, v = e.second;
            int num = abs(cnt[i][u]+cnt[u][v]+cnt[v][i]);//i,u,v组成的三角形(也可能是退化的三角形)内部包含的蓝点数
            int c[4] = {1, num, num*(num-1)/2, num*(num-1)*(num-2)/6};
            for(int j = 1; j <= 7; j++)
            {
                for(int k = 0; k <= 3; k++)
                {
                    if(!dp[u][j-1][k]) continue;
                    dp[v][j][k] = add(dp[v][j][k], dp[u][j-1][k]);
                    for(int x = 1; x+k <= 3; x++)
                        dp[v][j][x+k] = add(dp[v][j][x+k], mul(c[x], dp[u][j-1][k]));
                }
            }
        }
        ans = add(ans, dp[i][7][3]);
    }
    printf("%lld", ans);
    return 0;
}