标签

dfs

算法思路概述

给定平面上的若干条边，我们需要枚举每条边作为起始边，然后通过特定的规则（寻找"最右边"的边）逐步构建多边形。重复这一过程k次后，判断是否能形成一个符合条件的简单多边形。如果是，就将计数器加1。

关键概念解析

​​有向边处理​​： 将每条无向边拆分为两条有向边（即两个方向）。 每条有向边具有明确的起点（指向的点）和终点（指出的点）。 ​​"最右边"边的定义​​： 在当前有向边的上下文中，以边的终点为极点，以边的反向方向为极轴（即正方向指向边的起点）。 将所有与当前边终点相连的其他边（不包括当前边本身）进行极角排序。 极角最小的边即为"最右边"的边。 ​​极角排序规则​​： 以当前边的反向方向为基准（0度）。 其他边的极角是相对于该基准方向的角度，按逆时针方向计算。 极角最小的边即为在当前方向下"最右"的边。

#include <iostream>
#include <cstring>
#include <cstdio>
#define eps 1e-7
using namespace std;

// 全局布尔变量，初始值为true，具体用途未在代码中明确体现
bool tmp = 1;

// 定义点结构体Dot，用于表示平面上的点，包含x和y坐标
struct Dot
{
    double x, y;
    // 默认构造函数
    Dot () {}
    // 带参数的构造函数，用于初始化点的坐标
    Dot (double x, double y) : x(x), y(y) {}
    // 重载加法运算符，实现点的加法
    Dot operator + (Dot a)
    {
        return Dot (x + a.x, y + a.y);
    }
    // 重载减法运算符，实现点的减法
    Dot operator - (Dot a)
    {
        return Dot (x - a.x, y - a.y);
    }
} d[200];

// con是一个二维数组，作为邻接表存储图的边信息，con[i][0]存储点i的邻接边数量，con[i][j]（j > 0）存储点i的第j条邻接边连接的点的编号
int con[200][15];
// vis_e是一个二维布尔数组，用于标记哪些边已经被删除，vis_e[i][j]表示点i的第j条边是否已被删除
bool vis_e[200][15];
// vis_d是一个一维布尔数组，用于标记哪些点已经被删除，vis_d[i]表示点i是否已被删除
bool vis_d[200];
// insi是一个一维布尔数组，用于标记哪些点在当前正在构建的多边形内部，insi[i]表示点i是否在多边形内部
bool insi[200];
// n表示图中的点数，len即题目中的k（多边形的边数），start记录当前搜索的起始点
int n, len, start;
// graph是一个二维布尔数组，作为邻接矩阵存储图的边信息，graph[i][j]表示点i和点j之间是否有边
bool graph[200][200];
// anti是一个布尔变量，用于记录当前搜索路径中反向边是否都被删除
bool anti;

// 计算两个向量的叉积，用于判断方向（例如找最右边的边）
double cross (Dot g, Dot h)    
{
    return g.x * h.y - g.y * h.x;
}

// 计算两个向量的点积
double mul (Dot g, Dot h)    
{
    return g.x * h.x + g.y * h.y;
}

// 判断点s相对于向量g和h的位置，返回true表示s在g和h构成的右侧方向
bool right (Dot g, Dot h, Dot s)    
{
    double ss = cross (g, h);
    double f1 = mul (s, g);
    double f2 = mul (s, h);
    if (ss > eps)
        return 1;
    if (ss < -eps)
        return 0;
    if (f1 < f2)
        return 1;
    return 0;
}

// 深度优先搜索函数，从点u出发，沿着第g条边，当前路径长度为tmp，不断向右搜索构建多边形
bool dfs (int u, int g, int tmp)    
{
    int v = con[u][g];
    insi[v] = 0;
    vis_d[v] = 1;
    anti = anti & graph[v][u];    // 判断从v到u的反向边是否也被删除

    for (int i = 0; i < n; i++)
        if (cross(d[v] - d[u], d[i] - d[u]) > eps)
            insi[i] = 0;
    // 判断多边形内是否有点，根据叉积判断点i是否在边uv的右侧（多边形外）

    if (tmp == len)
    {
        if (v != start)
            return 0;
        int flag = 0;
        for (int i = 0; i < n; i++)
            flag = flag | insi[i];    // 多边形内不能有点，若insi[i]为true表示点i在多边形内
        if (!flag)
            vis_e[u][g] = 1,
            graph[u][v] = 1;
        return (flag ^ 1) & (anti ^ 1);    // 若多边形内无点且反向边都被删除，则返回true
    }

    int t = 0;
    for (int i = 0; i < con[v][0]; i++)
    {
        int w = con[v][i + 1];
        if (vis_d[w] || vis_e[v][i + 1] || w == u)
            continue;
        if (cross (d[u] - d[v], d[w] - d[u]) > -eps
            && (!t || right (d[w] - d[v], d[con[v][t]] - d[v], d[u] - d[v])))
                t = i + 1;
    }
    if (!t)
        return 0;
    int flag = dfs (v, t, tmp + 1);
    if (flag)
        vis_e[u][g] = 1,
        graph[u][v] = 1;
    return flag & (anti ^ 1);
}

int main()
{
    int ttt; 
    scanf("%d", &ttt);
    while (ttt--)
    {
        memset(con, 0, sizeof(con));
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            int x;
            scanf("%d", &x);
            x--;
            scanf("%lf %lf", &d[x].x, &d[x].y);
            scanf("%d",&con[x][0]);
            for (int j = 0; j < con[x][0]; j++)
            {
                scanf("%d", &con[x][j + 1]);
                con[x][j + 1]--;
            }
        }
        scanf("%d", &len);

        memset(graph, 0, sizeof (graph));
        memset(vis_e, 0, sizeof (vis_e));
        // 边删掉了就永远都不会再用了

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < con[i][0]; j++)
                if (!vis_e[i][j + 1])
                {
                    memset(vis_d, 0, sizeof(vis_d));
                    memset(insi, 1, sizeof(insi));
                    // 点要每次删除，因为一个点可能出现在多个简单多边形上

                    anti = 1;
                    start = i;
                    insi[i] = 0;
                    if (dfs(i, j + 1, 1))
                        ans++;
                }
        printf("%d\n", ans);
    }
}