#include #include #include using namespace std; class pt { public: int x,y; static pt src; pt(){}; void operator=(pt& a) { x = a.x; y = a.y; } pt(int a,int b):x(a),y(b){}; }; inline int cross(const pt& a ,const pt& b , const pt& c) { return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } int dist(const pt& a, const pt& b) { int t = a.x^2+a.y^2-b.x^2-b.y^2; return t; } struct cmp { bool operator()(const pt& a,const pt& b) { int re = cross(a,b,pt::src); if(re == 0) return dist(a,pt::src) return re>0; } };
int graham(vector& m, queue& q, int n) { //找最左下的 vector::iterator lowest=m.begin(),it; for(it=m.begin()+1; it!=m.end();it++) if(it->yy || it->y==lowest->y && it->xx) lowest = it; iter_swap(m.begin(),lowest); pt::src=m[0]; sort(m.begin()+1,m.end(),cmp()); q.push(m[0]); //坐标原点 int i = 1; while(i { while(i=0) i++; q.push(m[i++]); } }; pt pt::src(0,0); main() {