算法流程假设算法处理的平面点集存在不在同一直线上的三点1.找出y坐标最小的点,如果有多个这样的点,选取xxx坐标最小的点,记为ppp2.将除ppp以外的所有点按和ppp连线的极角排序,如果有多个不同的点位于同一极径上,只保留离ppp最远的点。将剩下的所有点按和ppp连线的极角大小从小到大记为{p1p_1p1​,p2p_2p2​,—pnp_npn​}3.将p1p_1p1​,p2p_2p2​,p3p_3p3​压入栈SSS4.对p4p_4p4​到pnp_npn​的当前点pjp_jpj​,如果pjp_jpj​和SSS栈顶顶点的连线和栈顶顶点和栈顶之下的顶点的连线构成严格左转关系则将pjp_jpj​入栈,继续处理下一个顶点pj1p_{j1}pj1​否则SSS弹出栈顶元素,对新的栈顶顶点和栈顶之下的顶点重复以上步骤直到构成严格左转入栈pjp_jpj​为止5.当最后一个顶点pnp_npn​处理完毕后,SSS从栈底到栈顶就是按逆时针存放的二维凸包的顶点C代码#includeiostream#includeutility#includevectorusingnamespacestd;intscalarProduct(intx1,inty1,intx2,inty2){returnx1*x2y1*y2;}intvectorProduct(intx1,inty1,intx2,inty2){returnx1*y2-x2*y1;}boolleft_turn(intx1,inty1,intx2,inty2){if(vectorProduct(x1,y1,x2,y2)0){returntrue;}returnfalse;}boolcompare(constpairint,intleft_down_point,constpairint,intleft,constpairint,intright){if(vectorProduct(left.first-left_down_point.first,left.second-left_down_point.second,right.first-left_down_point.first,right.second-left_down_point.second)0){returntrue;}if(vectorProduct(left.first-left_down_point.first,left.second-left_down_point.second,right.first-left_down_point.first,right.second-left_down_point.second)0){if(scalarProduct(left.first-left_down_point.first,left.second-left_down_point.second,left.first-right.first,left.second-right.second)0){returntrue;}}returnfalse;}voidQuickSort(vectorpairint,intseq,intleft,intright,constpairint,intleft_down_point){if(leftright)return;intmid(leftright)/2;if(compare(left_down_point,seq[left],seq[mid]))midleft;if(compare(left_down_point,seq[right],seq[mid]))midright;if(mid!left){swap(seq[mid],seq[left]);}if(compare(left_down_point,seq[mid],seq[right])){swap(seq[mid],seq[right]);}intileft;intjright;pairint,intpivotseq[right];while(ij){for(;ijcompare(left_down_point,pivot,seq[i])false;){i;}seq[j]seq[i];for(;ijcompare(left_down_point,seq[j],pivot)false;){--j;}seq[i]seq[j];}seq[i]pivot;QuickSort(seq,left,i-1,left_down_point);QuickSort(seq,i1,right,left_down_point);}voiddoGrahamScan(vectorpairint,intsorted_point,vectorintwork_stack){work_stack.push_back(0);work_stack.push_back(1);for(inti2;isorted_point.size();i){while(left_turn(sorted_point[i].first-sorted_point[work_stack.back()].first,sorted_point[i].second-sorted_point[work_stack.back()].second,sorted_point[work_stack.back()].first-sorted_point[work_stack[work_stack.size()-2]].first,sorted_point[work_stack.back()].second-sorted_point[work_stack[work_stack.size()-2]].second)false){work_stack.pop_back();}work_stack.push_back(i);}}intmain(){vectorpairint,intinput{{2,6},{2,5},{1,4},{3,4},{5,4},{6,4},{1,3},{2,3},{5,3},{7,3},{0,2},{3,2},{7,2},{8,2},{2,1},{6,1},{7,1},{9,1},{4,0},{6,0},{7,0}};inty_min;for(size_t i0;iinput.size();i){if(i0||input[i].secondy_min){y_mininput[i].second;}}intx_min;intmin_x_min_y_index-1;for(size_t i0;iinput.size();i)//这两个循环可以合并为一个循环可修改{if(input[i].secondy_min){if(min_x_min_y_index-1||input[i].firstx_min){x_mininput[i].first;min_x_min_y_indexi;}}}vectorintwork_stack;vectorpairint,intpoint_fartest;vectorpairint,intother_point(input.size()-1);for(size_t i0;iinput.size();i){if(istatic_castsize_t(min_x_min_y_index)){other_point[i]input[i];}elseif(istatic_castsize_t(min_x_min_y_index)){other_point[i-1]input[i];}}QuickSort(other_point,0,other_point.size()-1,{x_min,y_min});point_fartest.push_back(other_point[0]);for(size_t i1;iother_point.size();i){if(vectorProduct(other_point[i-1].first-x_min,other_point[i-1].second-y_min,other_point[i].first-x_min,other_point[i].second-y_min)!0){point_fartest.push_back(other_point[i]);}}doGrahamScan(point_fartest,work_stack);cout凸包上各点按逆时针方向排列为endl;coutxx_min yy_minendl;for(size_t i0;iwork_stack.size();i){coutxpoint_fartest[work_stack[i]].first ypoint_fartest[work_stack[i]].secondendl;}return0;}