算法流程:(1)首先找到最左下方的点AAA,即寻找yyy坐标最小的点,如果有多个这样的点则选取xxx坐标最小的一个,令i1i1i1,令AiA_iAi​为AAA,并把AAA加入凸包(2))iii自增1,找出这样的点AiA_iAi​:所有的点均位于线段Ai−1A_{i-1}Ai−1​AiA_iAi​的右侧(从Ai−1A_{i-1}Ai−1​向AiA_iAi​看去的方向)或线段Ai−1A_{i-1}Ai−1​AiA_iAi​上(除Ai−1A_{i-1}Ai−1​,AiA_iAi​以外)(3)若AiAA_iAAi​A则结束算法否则将AiA_iAi​加入凸包转(2)C代码#includeiostream#includevector#includeutilityusingnamespacestd;intcross(intx1,inty1,intx2,inty2){return(x1*y2-x2*y1);}intinnerProduct(intx1,inty1,intx2,inty2){returnx1*x2y1*y2;}intmain(){vectorpairint,intCH;vectorpairint,intpoint_can_be_selected{{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}};//重载运算符令其先按y从小到大排序再按x从小到大排序pairint,intstart_pointpoint_can_be_selected[0];for(size_t i1;ipoint_can_be_selected.size();i){if(start_point.secondpoint_can_be_selected[i].second){start_pointpoint_can_be_selected[i];}elseif(start_point.secondpoint_can_be_selected[i].second){if(start_point.firstpoint_can_be_selected[i].first){start_pointpoint_can_be_selected[i];}}}pairint,int_new_pointstart_point;do{pairint,intnext_new_point;boolflagfalse;for(vectorpairint,int::iterator runpoint_can_be_selected.begin();run!point_can_be_selected.end();run){if(*run_new_point)continue;if(flagfalse){flagtrue;next_new_point*run;}else{if(cross(run-first-_new_point.first,run-second-_new_point.second,next_new_point.first-_new_point.first,next_new_point.second-_new_point.second)0){next_new_point*run;}}}for(vectorpairint,int::iterator runpoint_can_be_selected.begin();run!point_can_be_selected.end();run){if(*run_new_point||*runnext_new_point)continue;if(cross(run-first-_new_point.first,run-second-_new_point.second,next_new_point.first-_new_point.first,next_new_point.second-_new_point.second)0){if(innerProduct(run-first-next_new_point.first,run-second-next_new_point.second,next_new_point.first-_new_point.first,next_new_point.second-_new_point.second)0){next_new_point*run;}}}CH.push_back(next_new_point);_new_pointnext_new_point;}while(start_point!_new_point);cout给定点集的凸包为endl;for(size_t i0;iCH.size();i){cout(CH[i].first,CH[i].second) ;}coutendl;return0;}