凸多边形三角划分

多边形的概念与分类概念：多边形是指由若干条线段首尾相连而构成的封闭几何图形。

其中，每条线段被称为多边形的边，边与边之间的交点被称为多边形的顶点。

多边形是平面几何中一种常见的形状，其形状可以通过边的数量和长度以及各个角的大小来确定。

分类：根据多边形的边数和角的性质，多边形可以分为以下几类：1. 三角形：三角形是由三条边和三个角组成的多边形。

三角形的边与角之间存在一定的关系，例如，三个内角的和总是等于180度。

根据边的长度，三角形又可以分为等边三角形、等腰三角形和普通三角形。

等边三角形的三条边长度相等，等腰三角形的两个边长度相等，而普通三角形则没有边长度相等的情况。

2. 四边形：四边形是由四条边和四个角组成的多边形。

根据边的性质，四边形可以分为矩形、正方形、平行四边形、菱形和梯形等几种类型。

矩形的所有角都是直角，正方形是边长相等的矩形，平行四边形的对边互相平行，菱形的所有边长相等，梯形有一对边是平行的。

3. 五边形及以上的多边形：当多边形的边数超过四条时，通常用“n边形”的形式来表示，表示边的数量为n。

五边形被称为五边形，六边形被称为六边形，以此类推。

这些多边形可以根据边的性质进一步分类，如凸多边形和凹多边形。

凸多边形指的是多边形的所有内角都小于180度，不会向内凹陷。

每两个顶点之间连线所得的外角都小于等于180度，所有外角的和等于360度。

例如三角形、四边形中的凸四边形等。

凹多边形则至少存在一个内角大于180度，部分区域向内凹陷。

其外角的总和仍等于360度。

例如五边形中的凹五边形等。

多边形是平面几何学中的重要概念，通过对多边形的分类了解，我们可以更深入地研究和解决与多边形相关的几何问题。

同时，多边形也在许多领域得到广泛应用，如建筑设计、计算机图形学等。

因此，对多边形的概念和分类有着深入的理解是十分重要的。

凸三角形剖分算法引言：凸三角形剖分算法是计算机图形学中的一个重要算法，用于将凸多边形分割成多个三角形。

凸三角形剖分算法在计算机图形学中有广泛的应用，如三维模型的渲染和物体表面的三角化等。

本文将介绍凸三角形剖分算法的原理、步骤以及应用。

一、凸三角形剖分算法的原理凸三角形剖分算法的原理是通过将凸多边形分割成多个三角形来表示其形状。

凸多边形是一个没有凹角的多边形，因此可以通过将顶点连接成三角形来表示其形状。

凸三角形剖分算法的目标是找到一种分割方式，使得分割后的三角形尽可能接近原来的凸多边形。

二、凸三角形剖分算法的步骤1. 找到凸多边形的一个顶点作为起始点。

2. 选择一个可见的相邻顶点，并将其与起始点连接成一条边。

3. 判断新连接的边是否与凸多边形的其他边相交，如果相交则进行下一步，否则转到步骤2。

4. 在相交的边上选择一个顶点作为新的起始点，并将其与之前的起始点连接成一条边。

5. 重复步骤3和步骤4，直到所有的边都被连接成三角形。

三、凸三角形剖分算法的应用1. 三维模型的渲染：凸三角形剖分算法可以将三维模型表面分割成多个三角形，从而方便进行渲染和光照计算。

通过将三维模型分割成三角形，可以更好地表示其形状和曲面细节。

2. 物体表面的三角化：在计算机图形学中，凸三角形剖分算法也常用于对物体表面进行三角化。

通过将物体表面分割成多个三角形，可以更好地描述物体的形状和曲面特征，方便进行后续的计算和分析。

3. 网格生成：凸三角形剖分算法可以用于生成网格，在计算机图形学中常用于网格建模和网格编辑等应用。

通过将凸多边形分割成多个三角形，可以更好地表示网格的形状和结构。

4. 地图生成：凸三角形剖分算法还可以应用于地图生成，特别是地形地图的生成。

通过将地形区域分割成多个三角形，可以方便地表示地形的高度和坡度等信息，为后续的地图渲染和分析提供基础数据。

结论：凸三角形剖分算法是计算机图形学中的一个重要算法，通过将凸多边形分割成多个三角形来表示其形状。

凸多边形的三角划分卡特林数凸多边形的三角划分问题是指如何将一个凸多边形划分成一些不重叠的三角形。

这个问题在计算几何中具有重要的应用，如有限元分析、多边形网格生成等。

卡特林数是解决凸多边形的三角划分问题的一种计数方法。

卡特林数是一个组合数列，其中第n个卡特林数表示将一个凸n+2边形划分成三角形的不同划分数目。

首先，我们来介绍一下卡特林数的递归关系。

设C(n)表示将一个凸n+2边形划分成三角形的不同划分数目。

我们可以考虑凸n+2边形的一个顶点，将其与其他n+1个顶点分别连接，得到n+1个划分情况。

如果选择的顶点与其他顶点构成一条对角线，那么我们将得到两个凸多边形，分别是一个边长为k+2的凸多边形和一个边长为n-k+1的凸多边形。

其中k的取值范围是0到n，表示选择的对角线一侧顶点的个数。

因此有递推关系式：C(n) = C(0) * C(n) + C(1) * C(n-1) + C(2) * C(n-2) + ...+ C(n) * C(0)其中，C(0) = C(1) = 1，表示一个凸2边形和一个凸3边形的划分数目均为1。

我们可以使用动态规划的方法求解卡特林数。

设一个数组C，其中C[i]表示C(i-2)。

我们从小到大计算C[i]，通过递推关系式可以得到C[n]的值。

最终，C[n]就表示了将一个凸n+2边形划分成三角形的不同划分数目。

利用卡特林数，我们可以解决一些与凸多边形的三角划分相关的问题。

例如，我们可以计算一个凸n+2边形的所有不同划分数目。

对于划分数目较大的情况，我们可以使用大数计算来解决。

另外，卡特林数也可以求解一些特定的凸多边形划分问题。

例如，给定一个凸n+2边形，我们希望找到一条对角线，使得将凸多边形划分成的两个子多边形中，其中一个子多边形有恰好k条边。

我们可以利用卡特林数的递归关系式，在计算中判断划分的结果是否满足要求。

在实际应用中，我们可以将凸多边形的三角划分问题转化为求解卡特林数的问题，并通过动态规划的方法来求解。

凸三⾓形最优三⾓剖分问题相关定义：(1)凸多边形的三⾓剖分：将凸多边形分割成互不相交的三⾓形的弦的集合T。

(2)最优剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三⾓形上的权函数w。

要求确定该凸多边形的三⾓剖分，使得该三⾓剖分中诸三⾓形上权之和为最⼩。

下图为剖分案例。

若凸(n+1)边形P={V0,V1……Vn}的最优三⾓剖分T包含三⾓形V0VkVn,1<=k<=n，则T的权为三个部分权之和：三⾓形V0V k V n的权，多边形{V0,V1……V k}的权和多边形{V k,V k+1……V n}的权之和。

如下图所⽰：可以断⾔，由T确定的这两个⼦多边形的三⾓剖分也是最优的。

因为若有{V0,V1……V k}和{V0,V1……V k}更⼩权的三⾓剖分，将导致T不是最优三⾓剖分的⽭盾。

因此，凸多边形的三⾓剖分问题具有最优⼦结构性质。

3、递推关系：设t[i][j],1<=i<j<=n为凸多边形{V i-1,Vi……Vj}的最优三⾓剖分所对应的权值函数值，即其最优值。

最优剖分包含三⾓形Vi-1VkVj的权，⼦多边形{Vi-1,Vi……Vk}的权，⼦多边形{Vk，Vk+1……Vj}的权之和。

因此，可得递推关系式：凸(n+1)边形P的最优权值为t[1][n]。

三⾓剖分的结构及其相关问题。

凸三⾓形的三⾓剖分与表达式的完全加括号之间具有⼗分密切的关系。

正如所看到的⼀样，矩阵连乘的最优计算次序等价于矩阵链的最优完全加括号⽅式。

其实更加奇妙的地⽅是，这些问题似乎都是⼀个模⼦刻出来的！其实本质原因就是因为它们所对应的完全⼆叉树的同构性。

⼀个表达式的完全加括号⽅式相应于⼀棵完全⼆叉树，称为表达式的语法树。

⽽恰恰恰好的是，凸多边形的剖分也可以⽤语法数表⽰。

（请原谅“草滩⼩恪”画图功夫不⾏，⽆法画出对应的图） 模板主要代码：//t[][] 记忆路径， s[][] 记录最优路径 W（，，）为权值函数const int maxn = 100;void minWeightTriangulation(int n, int t[][100], int s[][100]){for(int i=1; i<=n; i++) t[i][i] = 0;for(int r=2; r<=n; r++)for(int i=1; i<=n-r+1; i++){int j = i + r - 1;t[i][j] = t[i+1][j] + w(i-1, i, j);s[i][j] = i;for(int k = i+1; k<j; k++){int u = t[i][k] + t[k+1][j] + w(i-1, k, j);if(u<t[i][j]){t[i][j] = u;s[i][j] = k;}}}}代码如有疑问可参见“矩阵连乘”。

c++凸多边形的三角形剖分
C++中凸多边形的三角形剖分是一个常见的计算几何问题，可以通过多种方法来实现。

三角形剖分是将凸多边形分解为一系列不相交的三角形的过程，常用于图形渲染、碰撞检测和有限元分析等领域。

一种常见的方法是使用三角形扇剖分法，它从凸多边形的一个顶点开始，依次连接相邻顶点，将凸多边形分解为一系列三角形。

在C++中，可以通过遍历凸多边形的顶点，并使用C++中的数据结构（如数组、向量等）来存储和操作顶点信息，以及计算三角形的顶点索引，从而实现三角形扇剖分。

另一种常见的方法是使用Ear Clipping 算法，它通过逐步移除凸多边形的耳朵（一个顶点及其相邻的两条边），将凸多边形分解为一系列三角形。

在C++中，可以通过实现Ear Clipping算法的逻辑，遍历凸多边形的顶点，识别和移除耳朵，并构建三角形，来实现凸多边形的三角形剖分。

此外，还可以使用Delaunay 三角网格生成算法，它可以将凸多边形分解为一组无重叠的三角形，并且最小化了三角形的不良形
状。

在C++中，可以使用现有的Delaunay 三角网格生成算法的库来实现凸多边形的三角形剖分。

总之，在C++中实现凸多边形的三角形剖分，可以根据具体需求选择合适的方法，并结合C++的数据结构和算法来实现。

这些方法都需要考虑凸多边形的顶点顺序、边界情况以及三角形的顶点索引等细节，以确保准确和高效地进行三角形剖分。

凸多边形的性质及分类凸多边形是指多边形中所有的内角都小于180度的多边形。

本文将介绍凸多边形的一些基本性质，并对凸多边形进行分类。

一、凸多边形的性质1. 内角和公式：一个凸多边形的n个内角的和可以用公式计算出来，即和 = (n - 2) × 180度。

2. 外角和公式：一个凸多边形的n个外角的和总是等于360度。

3. 对角线数量：一个具有n个顶点的凸多边形，其对角线的数量可以通过公式来计算，即对角线数量 = n × (n - 3) / 2。

4. 顶点数量：一个凸多边形有n个顶点。

5. 边的数量：一个凸多边形有n个边。

二、凸多边形的分类凸多边形根据边的数量可以分为三类：三角形、四边形和五边形以上的多边形。

下面分别介绍这三类凸多边形的特点。

1. 三角形三角形是一种具有三个边和三个顶点的凸多边形。

根据角度的不同，三角形可以分为锐角三角形、直角三角形和钝角三角形。

其中，锐角三角形的三个内角都小于90度，直角三角形有一个内角为90度，而钝角三角形则至少有一个内角大于90度。

2. 四边形四边形是一种具有四个边和四个顶点的凸多边形。

根据边的长度和角度的不同，四边形可以分为矩形、正方形、平行四边形、菱形和梯形。

- 矩形：矩形的四个内角都是直角(90度)，且相对边长度相等。

- 正方形：正方形是一种特殊的矩形，四个内角都是直角(90度)，且四条边长度相等。

- 平行四边形：平行四边形是具有两对对边平行的四边形。

- 菱形：菱形是具有对边相等、内角为直角(90度)的四边形。

- 梯形：梯形是具有一对平行边的四边形。

3. 五边形以上的多边形五边形以上的多边形可以根据边的长度和角度的不同进行进一步的分类。

一般而言，这些多边形具有不同长度和不同角度的边，且很多凸多边形都有自己的专有名称，如六边形、七边形、八边形等等。

结论凸多边形是一种具有许多有趣性质的几何形状，其性质和分类可以通过数学方法进行研究和推导。

通过了解凸多边形的性质，我们可以更好地理解和应用它们在几何学和实际问题中的作用。

凸多边形最优三⾓剖分相关概念凸多边形：当⼀个简单多边形及其内部构成⼀个闭凸集时，则称该简单多边形为⼀个凸多边形。

即凸多边形边界上或内部的任意两点所连成的直线段上所有点均在凸多边形的内部或边界上。

通常，⽤多边形顶点的逆时针序列表⽰凸多边形，即表⽰具有 n 条边，的凸多边形。

其中，约定。

弦：若与是多边形上不相邻的两个顶点，则线段称为多边形的⼀条弦。

弦将多边形分割成两个多边形和。

多边形的三⾓剖分三⾓剖分多边形的三⾓剖分是将多边形分割成互不相交的三⾓形的弦的集合 T。

下图为⼀个凸 7 边形的两个不同的三⾓剖分。

在凸多边形 P 的⼀个三⾓剖分 T 中，各弦互不相交，且集合T 已达到最⼤，即 P 的任⼀不在 T 中的弦必与 T 中某⼀弦相交。

在有 n 个顶点的凸多边形中，恰有 (n-3) 条弦和 (n-2) 个三⾓形。

最优三⾓剖分给定凸多边形，以及定义在由凸多边形的边和弦组成的三⾓形上的权函数 w ，要求确定该凸多边形的三⾓剖分，使得该三⾓剖分所应对的权，即三⾓剖分中诸三⾓形上权之和为最⼩。

最优⼦结构性质凸多边形的最优三⾓剖分问题有最优⼦结构性质。

事实上，若凸 (n+1) 边形，的最优三⾓剖分 T 包含三⾓形，则 T 的权为三⾓形的权，⼦多边形和的权之和。

可以断⾔，由 T 确定的这两个⼦多边形的三⾓剖分也是最优的。

因为若有和的更⼩权的三⾓剖分，将导致 T 不是最优三⾓剖分⽭盾。

最优三⾓剖分的递归结构令为凸⼦多边形的最优三⾓剖分对应的权函数值，即其最优值。

实现#include <bits/stdc++.h>using namespace std;const int N=7;int s[N][N],t[N][N],weight[][N]={{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0}};int dp(int n);void Traceback(int i,int j);int Weight(int a,int b,int c);int main(){cout<<"此多边形的最优三⾓剖分值为："<<dp(N-1)<<endl;cout<<"最优三⾓剖分结构为："<<endl;Traceback(1,N-2);system("pause");return0;}int dp(int n){int i,r,j,k,u;for(i=1;i<=n;i++) t[i][i] = 0;for(r=2;r<=n;r++){for(i=1;i<=n-r+1;i++){j=i+r-1;t[i][j]=t[i+1][j]+Weight(i-1,i,j);s[i][j]=i;for(k=i+1;k<j;k++){u =t[i][k]+t[k+1][j]+Weight(i-1,k,j);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}}return t[1][N-2];}void Traceback(int i,int j){if(i==j) return;Traceback(i,s[i][j]);Traceback(s[i][j]+1,j);cout<<"三⾓剖分顶点：V"<<i-1<<",V"<<j<<",V"<<s[i][j]<<endl; }int Weight(int a,int b,int c){return weight[a][b]+weight[b][c]+weight[a][c];}。

三角剖分准则三角剖分是计算机图形学中常用的一种技术，用于将一个复杂的几何图形划分为一系列简单的三角形。

三角剖分的准则是指在进行三角剖分时需要遵循的一些原则和规则，以保证生成的三角形具有一定的质量和准确性。

一、凸多边形剖分准则对于一个凸多边形，可以通过在顶点之间连接边来剖分为一系列三角形。

剖分准则要求剖分后的三角形不能相交，每个三角形的内角和应该等于180度。

二、非凸多边形剖分准则对于一个非凸多边形，剖分时需要注意以下几点：1. 任意两个顶点之间的连线不应该穿过多边形的内部，即不应该与多边形的边相交。

2. 任意两个相邻的三角形之间的边不应该相交。

3. 三角形的内角和仍然应该等于180度。

三、Delaunay三角剖分准则Delaunay三角剖分是一种常用的三角剖分方法，它具有一定的优势和特点。

Delaunay三角剖分的准则如下：1. 任意两个相邻的三角形之间的外接圆不应该包含任何其他顶点。

2. 任意一个顶点的相邻三角形的外接圆不应该包含该顶点的任何其他相邻顶点。

3. 三角形的内角和仍然应该等于180度。

Delaunay三角剖分的几何特性使得它在计算机图形学中得到广泛应用，例如在三维建模、地理信息系统和计算机辅助设计等领域。

Delaunay三角剖分的准则保证了生成的三角形具有最大的最小角度，从而提高了三角网格的质量和精度。

四、约束三角剖分准则约束三角剖分是指在进行三角剖分时需要考虑一些额外的约束条件，如边界约束、角度约束等。

约束三角剖分的准则如下：1. 边界约束：剖分的三角形要与给定的边界一致，即边界上的点应该在同一个三角形内。

2. 角度约束：剖分的三角形的最小角度和最大角度应该在一定的范围内。

约束三角剖分可以根据实际需求进行定制，以满足具体的应用场景和要求。

例如在有限元分析中，可以通过约束三角剖分来控制网格的形状和大小，从而提高分析的准确性和效率。

三角剖分准则是进行三角剖分时需要遵循的一些原则和规则，以保证生成的三角形具有一定的质量和准确性。

凸多边形最优三角剖分的最小弦长大家好，今天我们来聊聊一个有趣的话题：凸多边形最优三角剖分的最小弦长。

这个问题听起来有点高深，但其实它就是让我们去找出一种方法，把一个凸多边形分成若干个三角形，使得这些三角形的总周长最小。

这个问题在数学上叫做“平面三角剖分”，是一个非常经典的问题。

那么，这个问题有什么实际应用呢？其实它在很多领域都有用处，比如建筑设计、地理信息系统等等。

下面我们就来详细讲解一下这个问题。

我们要明确一点：凸多边形是什么样的图形呢？凸多边形就是指在一个平面上，由若干个点组成的封闭图形，其中任意两点之间的距离都小于它们之间的线段长度。

换句话说，凸多边形就是一个顶点都在内部的封闭图形。

这样的图形有很多特点，比如它的边界是光滑的，没有凹陷的地方；它的内部是空心的，没有实心的部分；它的面积和周长都是有限的等等。

接下来，我们就要想办法把这个凸多边形分成若干个三角形。

这个问题的关键在于如何找到一个合适的划分方法。

我们知道，一个三角形有三条边，而一个凸多边形有无数条边。

如果我们随便把这个多边形分成若干个小三角形，那么这些小三角形的总周长可能会很大。

所以我们需要找到一种方法，让这些小三角形尽可能地接近彼此，从而使得整个划分方案的总周长最小。

为了解决这个问题，我们可以先从一个简单的问题开始思考：如何把一个三角形分成两个更小的三角形？答案很简单，只要在三角形的一条边的中点处画一条线段即可。

这样一来，原来的大三角形就被分成了两个小三角形，而且这两个小三角形的总周长之和等于原来大三角形的周长减去这条中线段的长度。

这个结论对于任意形状的三角形都是成立的。

那么，对于一个凸多边形来说，我们能不能也用同样的方法来把它分成若干个更小的三角形呢？答案是肯定的。

我们只需要沿着凸多边形的边界一直画线段，直到把它分成若干个小多边形为止。

然后再对每个小多边形重复上面的步骤，把它分成更小的多边形。

这样一来，我们就可以得到一个无穷级数的结果：凸多边形被分成了若干个越来越小的三角形。

凸多边形三⾓划分题⽬描述给定⼀个具有N（N<50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。

问如何把这个凸多边形划分成N－2个互不相交的三⾓形，使得这些三⾓形顶点的权的乘积之和最⼩？这应该怎么计算呢？输⼊第⼀⾏为顶点数N，第⼆⾏为 N个顶点（从1到N）的权值。

输出第⼀⾏为最⼩的和的值。

第⼆⾏为各三⾓形组成的⽅式。

各三⾓形各顶点之间以空格间隔，顶点从⼩到⼤排序，三⾓形之间从左到右按字典序排序，中间的逗号为半⾓字符。

样例输⼊5121 122 123 245 231样例输出122148841 2 3，1 3 5，3 4 5 剖分问题，找最后⼀个决策点就⾏了，注意要输出⽅案。

设dp[i][j]表⽰从i到j进⾏三⾓形划分能得到的最⼤值，显然有dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+val[i]*val[j]*val[k])枚举分割点k，时间复杂度O(n^3). 注意写⾼精度 上代码。

1 #include<bits/stdc++.h>2#define mod 100003#define maxn 3054#define N 1055using namespace std;6struct HP {7int len;8long long p[maxn];9 HP &operator = (const char *);10 HP &operator = (long long);11 HP(){memset(p,0,sizeof(p));len=1;}12 HP(long long);1314bool operator >(const HP &) const;15bool operator <(const HP &) const;16bool operator <=(const HP &) const;17bool operator >=(const HP &) const;18bool operator !=(const HP &) const;19bool operator ==(const HP &) const;2021 HP operator + (const HP &) const;22 HP operator - (const HP &) const;23 HP operator * (const HP &) const;24 HP operator / (const HP &) const;25 HP operator % (const HP &) const;2627 HP &operator +=(const HP &);28 HP &operator -=(const HP &);29 HP &operator *=(const HP &);30 HP &operator /=(const HP &);31 HP &operator %=(const HP &);32 };33 HP & HP::operator = (const char *str) {34 memset(p,0,sizeof(p));35int n=strlen(str),j=1,k=1;36for(int i=1;i<=n;i++){37if(k==mod) j++,k=1;38 p[j]+=k*(str[n-i]-'0');39 k*=10;40 }41 len=j;42return *this;43 }44 HP & HP::operator = (long long num) {45char s[101];46 sprintf(s,"%d",num);47return *this=s;48 }49 HP::HP(long long num) {*this=num;}50bool HP::operator <(const HP &a)const {51if(len<a.len) return1;52else if(len>a.len) return0;53else {54int i=len;55while(i>=1) {56if(p[i]<a.p[i]) return1;57else if(p[i]>a.p[i]) return0;58else i--;59 }60return0;61 }62 }63bool HP::operator >(const HP &b) const {return b<*this;}64bool HP::operator <=(const HP &b) const {return !(*this>b);}65bool HP::operator >=(const HP &b) const {return !(*this<b);}66bool HP::operator !=(const HP &b) const {return (b<*this)||(*this<b);}67bool HP::operator ==(const HP &b) const {return !(*this<b)&&!(b<*this);} 6869 HP HP::operator + (const HP &b)const {70 HP c;71 c.len=len>b.len?len:b.len;72int i=1;73while(i<=c.len) {74 c.p[i]+=p[i]+b.p[i];75if(c.p[i]>=mod) {76 c.p[i+1]++,c.p[i]-=mod;77 }78 i++;79 }80if(c.p[c.len+1]>0) c.len++;81return c;82 }83 HP HP::operator -(const HP &b)const{ //a-b84 HP c;85 c.len=len;86for(int i=1; i<=c.len; i++) {87 c.p[i]+=p[i]-b.p[i];88if(c.p[i]<0) {89 c.p[i]+=mod;90 c.p[i+1]--;91 }92 }93while(c.p[c.len]==0&&c.len>1) c.len--;94return c;95 }96 HP &HP::operator +=(const HP &b) {return *this=*this+b;}97 HP &HP::operator -=(const HP &b) {return *this=*this-b;}98 HP HP::operator *(const HP &b)const{99 HP c;100int i=1,j=1,k=1;101 c.len=len+b.len+1;102while(i<=len) {103 k=i;104 j=1;105while(j<=b.len) {106 c.p[k]+=p[i]*b.p[j];107if(c.p[k]>=mod) {c.p[k+1]+=c.p[k]/mod,c.p[k]%=mod;}108 k++,j++;109 }110 i++;111 }112while(c.p[c.len]==0&&c.len>1) c.len--;113return c;114 }115 HP &HP::operator *=(const HP &b){return *this=*this*b;}116 HP HP::operator /(const HP &b)const { // a/b117 HP c,d;118 c.len=len;119 d.len=0;120for(int i=len; i>=1; i--) {121 d=d*HP(mod)+p[i];122long long left=0,right=9999,mid;123while(left<right) {124 mid=(left+right)/2;125if(b*HP(mid)<=d) left=mid+1;126else right=mid;127 }128long long ans1=right-1;129long long ans2=right;130if(HP(ans2)*b<=d) ans1=ans2;131 c.p[i]=ans1;132 d=d-b*HP(ans1);133 }134while(c.p[c.len]==0&&c.len>1) c.len--;135return c;136 }137 HP HP::operator %(const HP &b)const {138 HP c,d;139 c.len=len+b.len+1;140 d.len=0;141for(int i=len; i>=1; i--) {142 d=d*HP(mod)+p[i];143long long left=0,right=9999,mid;144while(left<right) {145 mid=(left+right)/2;146if(b*HP(mid)<=d) left=mid+1;147else right=mid;148 }149long long ans1=right-1;150long long ans2=right;151if(HP(ans2)*b<=d) ans1=ans2;152 c.p[i]=ans1;153 d=d-b*HP(ans1);154 }155while(c.p[c.len]==0&&c.len>1) c.len--;156return d;157 }158 HP &HP::operator /=(const HP &b){*this=*this/b;}159 HP &HP::operator %=(const HP &b){*this=*this%b;}160 ostream & operator << (ostream &o,HP &n) {161 o<<n.p[n.len];162for(int i=n.len-1; i>=1; i--) {163 o.width(4);164 o.fill('0');165 o<<n.p[i];166 }167return o;168 }169 istream & operator >> (istream & in,HP &n) {170char s[maxn];171in>>s;172 n=s;173return in;174 }175//前⾯是⾼精度模板176177 HP s[N];//保存节点的数组也要有⾼精度！！之前⼀直没注意，两个点⼀直WA178 HP dp[N][N];179struct ANS{180int x,y,z;181bool operator <(const ANS&t)const{182if(x!=t.x) return x<t.x;183if(y!=t.y) return y<t.y;184if(z!=t.z) return z<t.z;185 }186 }res[N];//res数组保存的是我们最终的分解⽅案187int ans[N][N];//ans[i][j]表⽰将i节点，j节点，ans[i][j]节点划分为⼀个三⾓形188int ct;189 inline void dfs(int x,int z){190if(ans[x][z]==0) return ;191 res[++ct].x=x,res[ct].y=ans[x][z],res[ct].z=z;192 dfs(x,ans[x][z]),dfs(ans[x][z],z);193 }//递归求解⽅案。