企业官网建设流程全解析

算法流程:
(1)首先找到最左下方的点AAA,即寻找yyy坐标最小的点,如果有多个这样的点则选取xxx坐标最小的一个,令i=1i=1i=1,令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)若Ai==AA_i==AAi​==A则结束算法，否则将AiA_iAi​加入凸包转(2)

C++代码

#include<iostream>#include<vector>#include<utility>usingnamespacestd;intcross(intx1,inty1,intx2,inty2){return(x1*y2-x2*y1);}intinnerProduct(intx1,inty1,intx2,inty2){returnx1*x2+y1*y2;}intmain(){vector<pair<int,int>>CH;vector<pair<int,int>>point_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从小到大排序pair<int,int>start_point=point_can_be_selected[0];for(size_t i=1;i<point_can_be_selected.size();++i){if(start_point.second>point_can_be_selected[i].second){start_point=point_can_be_selected[i];}elseif(start_point.second==point_can_be_selected[i].second){if(start_point.first>point_can_be_selected[i].first){start_point=point_can_be_selected[i];}}}pair<int,int>_new_point=start_point;do{pair<int,int>next_new_point;boolflag=false;for(vector<pair<int,int>>::iterator run=point_can_be_selected.begin();run!=point_can_be_selected.end();++run){if(*run==_new_point)continue;if(flag==false){flag=true;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(vector<pair<int,int>>::iterator run=point_can_be_selected.begin();run!=point_can_be_selected.end();++run){if(*run==_new_point||*run==next_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_point=next_new_point;}while(start_point!=_new_point);cout<<"给定点集的凸包为"<<endl;for(size_t i=0;i<CH.size();++i){cout<<"("<<CH[i].first<<","<<CH[i].second<<") ";}cout<<endl;return0;}