分治法解题思路1、求横坐标最大和最小的两点p1和p2形成的直线。用这条直线把点集分成上下两部分set1和set2。上半部划分：2、从set1和set2中分别找出由线段p1p2构成的面积最大的三角形的点p3和p4。3、从set1边上找到直线p1p3左边的点集leftset1和直线p3p2右边的点集rightset1。4、对leftset1和leftset2重复步骤2和3，直到找不到直线外侧的点为止。下半部划分：5、从set2中，求直线p1p4左侧的点集leftset2，直线p3p4右侧的点集rightset2。6.对leftset1和leftset2重复步骤2和3，直到发现直线没有变化为止。外点。Merge：其实在合并之前，答案已经生成了，只是答案点集是不需要的，现在让其顺时针排列。点和线的位置可以通过下面的行列式的正负值来判断。它们之间的位置关系，取值是点和线段围成的三角形的面积：下面画图过程的动态图可以加深理解。思路是递归地把整体分成两半，递归地为每一半区域找一个点，使它和分界线组成的三角形面积最大，直到在这一半区域的分界线外找不到点为止形成一个三角形，则这半个区域停止，回溯到前半个区域继续处理...codeimportrandomimportmatplotlib.pyplotaspltimportmatplotlib.animationasanimationdraw_line_lists=[]#根据三者的坐标计算三角形面积三角形的顶点defcalc_area(a,b,c):x1,y1=ax2,y2=bx3,y3=c返回x1*y2+x3*y1+x2*y3-x3*y2-x2*y1-x1*y3#在(start,end)区间内，随机生成一个有n个点的点集(return:list[(x1,y1)...(xn,yn)])defsample(n,start=0,end=101):returnlist(zip([random.randint(start,end)for_inrange(n)],[random.randint(start,end)for_inrange(n)]))defUp(left,right,points,borders):"""找到第e上半边边界点:paramleft:tuple,最左边的点:paramright:tuple,最右边的点:parampoints:allpointsets:paramborders:borderpointset:return:"""#用于绘制，记录处理步骤draw_line_lists.append(left)draw_line_lists.append(right)#left和right_point两点组成一条直线，现在想在这条直线上找一个点，要求的三角形面积最大area_max=0#以points为单位记录item最大三角形的面积：ifitem==leftoritem==right:#构成直线的两个点也在lists集合中，但是不在直线上，所以不计算continueelse:temp=calc_area(left,right,item)#暂存点和线构成的面积，用于下次迭代比较iftemp>area_max:max_point=item#记录当前构成最大三角形的点area_max=temp#记录当前最大三角形面积ifarea_max!=0:#这实际上是递归边界。当一条直线上面没有可以测试的点时，停止，返回上层，处理他兄弟节点的子树。borders.append(max_point)Up(left,max_point,points,borders)#保持原来的左边界点不变，用刚刚找到的组成最大三角形的点作为右边界点，继续递归Up(max_point,right,points,borders)#原来的右边界点不变，新找到的构成最大三角形的点作为左边界点，继续递归defDown(left,right,points,borders):"""同Up中的参数"""#画图，记录处理步骤draw_line_lists.append(left)draw_line_lists.append(right)#left和right_point两点形成一条直线，现在想在这个下面找一个点直线，需要形成的三角形面积最大area_max=0#记录iteminpoints中最大三角形的面积：ifitem==leftoritem==right:#构成的两个点直线上也在列表集合中，但它们不是联合国der直线，所以不计算continueelse:temp=calc_area(left,right,item)#暂存点和线形成的面积，用于下一次迭代比较iftempmax(first_y,last_y):#如果y值大于最左边和最右边的点，必须在上半区up_borders.append(item)elifmin(first_y,last_y)0:up_borders.append(item)else:dowm_borders.append(item)else:#如果y值小于最左边和最右边的点，必须在下半区dowm_borders.append(item)list_end=up_borders+dowm_borders[::-1]#最终顺时针输出边界点returnlist_enddefdraws(points,list_frames,gif_name="save.gif"):"""生成动态图并保存:parampoints:allpointsets:paramlist_frames:framelist:paramgif_name:保存的Gif名称:return:.gif"""min_value=0max_value=100all_x=[]all_y=[]foriteminpoints:a,b=itemall_x.append(a)all_y.append(b)fig,ax=plt.subplots()#生成轴和图，可迭代对象x,y=[],[]#用于接受更新的数据线,=plt.plot([],[],color="red")#画线对象，plot返回值类型，加逗号definit():#初始化函数是用于绘制干净的画布，为后续绘制做准备ax.set_xlim(min_value-abs(min_value*0.1),max_value+abs(max_value*0.1))#初始函数，设置绘图范围ax.set_ylim(min_value-abs(min_value*0.1),max_value+abs(max_value*0.1))returnlinedefupdate(points):a,b=pointsx.append(a)y.append(b)line.set_data(x,y)returnlineplt.scatter(all_x,all_y)#绘制所有散点ani=animation.FuncAnimation(fig,update,frames=list_frames,init_func=init,interval=1500)#interval代表绘制连接的速度，值越大速度越慢ani.save(gif_name,writer='pillow')defshow_result(points,results):"""绘图：参数点：所有点集：参数结果：所有边集：返回：图片“””all_x=[]all_y=[]foriteminpoints：a，b=itemall_x.append（a）all_y.append（b)foriinrange(len(results)-1):item_1=results[i]item_2=results[i+1]#横坐标，纵坐标one_,oneI=item_1two_,twoI=item_2plt.plot([one_,two_],[oneI,twoI])plt.分散（all_x，all_y）plt.show()如果__name__=="__main__":points=[(101,47),(32,40),(21,90),(65,100),(98,64),(81,43),(51,20),(75,82),(90,34),(38,101)]#points=sample(100)#随机生成的点points.sort()#首先按x轴排序,用来求最左边和最右边的点borders=[]#边界点设置Up(points[0],points[-1],points,borders)#上边界点设置Down(points[0],points[-1)],points,borders)#下边界点集borders.append(points[0])borders.append(points[-1])#将第一个和最后两个点添加到边界点集results=order_border(borders)#orderClockwiseboundarypointprint(results)#顺时针输出答案results.append(results[0])#将最后一个点与源点连接起来，绘制闭合连接（仅在绘制时）show_result(points,results)#显示静态resultsdraws(points,results,"result.gif")#绘制动态resultsdraws(points,draw_line_lists,"process.gif")#绘制动态过程s程序运行结果输入坐标点[(101,47),(32,40),(21,90),(65,100),(98,64),(81,43),(51,20),(75,82),(90,34),(38,101)]输出动态绘制过程输出连接点顺序[(38,101),(65,100),(98,64),(101,47),(90,34),(51,20),(32,40),(21,90)]静态输出Outputthelargestconvexpolygon动态输出最大凸多边形
