输入数据及输出数据 问题分析 第一行为三个整数MN(1≤MN≤50)和K(0≤K≤296) ◆这是一道数区域的个数的题 以下行,每行四个数Cx1uY,1,X12Y1,2)表示一次切 ◆三角形的个数似乎应该与交点的个数有关 输出 一个整数切割后得到的三角形的个数 0个交点 2个三角形 个交点 1个三角形 枚举算法 问题分析 ◆基于点的枚举 ◆计算出所有的多边形判断其是否为三角 流行算法 ◆基于线的枚举 ◆基于块的枚举 ◆优化 例如分治 问题分析 三角形的分类 ◆问题规模很小,0≤M,N≤50 ◆按对角线的方向来分 ◆对于计算机而言如果它能够像人一样数 三角形那解决这个问题就很容易 所以我们只要教会计算机怎么数就可以 团4令 ◆用搜索的办法枚举出所有的三角形7 输入数据及输出数据 输入: 第一行为三个整数M,N(1≤M,N≤50)和K(0≤K≤296). 以下K行,每行四个数(Xi,1,Yi,1,Xi,2,Yi,2)表示一次切 割,(Xi,1,Yi,1)和(Xi,2,Yi,2)是金属板边缘上的两点. 输出: 一个整数,切割后得到的三角形的个数. 问题分析 Š 这是一道数区域的个数的题. Š 三角形的个数似乎应该与交点的个数有关. 0个交点 2个三角形 1个交点 1个三角形 没有明显的规律 枚举算法 Š 基于点的枚举 „ 流行算法 Š 基于线的枚举 Š 基于块的枚举 Š 优化 „ 例如分治 问题分析 Š 计算出所有的多边形,判断其是否为三角 形 看来很复杂 问题分析 Š 问题规模很小,0≤M, N≤50. Š 对于计算机而言,如果它能够像人一样数 三角形,那解决这个问题就很容易. Š 所以,我们只要教会计算机怎么数就可以 了. Š 用搜索的办法枚举出所有的三角形 三角形的分类 Š 按对角线的方向来分