学步园

#include <iostream><br /> #include <queue><br /> #include <vector><br /> #include <stack><br /> using namespace std;</p> <p>//点结构体<br /> typedef struct<br /> {<br /> int x,y;<br /> }Point;</p> <p>//左下角点Po<br /> Point leftBotm;</p> <p>//极角比较函数<br /> int leftTurn(Point p1,Point p2,Point p3) //p1:next-top, p2:top(), p3:pi<br /> {<br /> int ret=(p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y);<br /> if(ret<0)<br /> {<br /> return -1; //左转<br /> }<br /> else if(ret==0)<br /> {<br /> return 0; // 共线<br /> }<br /> else<br /> {<br /> return 1; //右转<br /> }<br /> }</p> <p>//仿比较函数结构体<br /> struct compare<br /> {<br /> bool operator()(const Point &p,const Point &q)<br /> {<br /> int ret=leftTurn(leftBotm,p,q);<br /> if(ret==-1)<br /> {<br /> return false;<br /> }<br /> else if(ret==1)<br /> {<br /> return true;<br /> }<br /> else<br /> {<br /> int minus=(p.x-leftBotm.x)*(p.x-leftBotm.x)-(q.x-leftBotm.x)*(q.x-leftBotm.x);<br /> if(minus<0)<br /> {<br /> return false;<br /> }<br /> else<br /> {<br /> return true;<br /> }<br /> }<br /> }<br /> };</p> <p>//最小堆<br /> typedef priority_queue<Point,vector<Point>,compare> minHeap;</p> <p>int main()<br /> {<br /> minHeap heap;<br /> int n;<br /> Point input;<br /> vector<Point> final;</p> <p> cin>>n;<br /> int x,y,k;<br /> cin>>input.x>>input.y;<br /> final.push_back(input);<br /> x=input.x;<br /> y=input.y;<br /> k=0;</p> <p> for(int i=1;i<n;++i)<br /> {<br /> cin>>input.x>>input.y;<br /> final.push_back(input);<br /> if(input.x<=x&&input.y<=y)<br /> {<br /> x=input.x;<br /> y=input.y;<br /> k=i;<br /> }<br /> }</p> <p> leftBotm.x=x;<br /> leftBotm.y=y;</p> <p> for(int i=0;i<n;++i)<br /> {<br /> if(i!=k)<br /> {<br /> heap.push(final[i]);<br /> }<br /> }</p> <p> Point pre,now;</p> <p> pre=heap.top();<br /> heap.pop();<br /> final.clear();</p> <p> while(!heap.empty())<br /> {<br /> now=heap.top();<br /> heap.pop();</p> <p> if(leftTurn(leftBotm,pre,now)==0)<br /> {<br /> pre=now;<br /> }<br /> else<br /> {<br /> final.push_back(pre);<br /> pre=now;<br /> }<br /> }</p> <p> final.push_back(pre);<br /> /*<br /> 全部已经按极角整理完毕,重复角只保留距离最远的<br /> */</p> <p> stack<Point> s;<br /> s.push(leftBotm);<br /> s.push(final[0]);<br /> s.push(final[1]);</p> <p> for(int j=2;j<(int)final.size();++j)<br /> {<br /> while(leftTurn(s._Get_container()[s.size()-2],s._Get_container()[s.size()-1],final[j])!=-1)<br /> {<br /> s.pop();<br /> }<br /> s.push(final[j]);<br /> }</p> <p> cout<<endl;</p> <p> for(int k=0;k<(int)s.size();++k)<br /> {<br /> cout<<s._Get_container()[k].x<<","<<s._Get_container()[k].y<<endl;<br /> }<br /> return 0;<br /> }</p> <p>