凸包问题的Braham扫描算法,极角排序

#include
#include
#include
#include
#include
#include
using namespace std;
//复合类型都自己定义比较操作符的,基本类型才用仿函数的
class point
{
public:
    int x,y;    
    static  point src;
    point()
    {
        x=y=0;
    }
    point(int a,int b)
    {
        x=a;
        y=b;
    }
    void operator=( point & a)
    {
        x = a.x;
        y = a.y;
    }
    friend int cross_product(const point&  a,const point& b,const point& c);
    //在对手的顺时针一侧则为真
    bool operator<(const point & a) const
    {    
        int res = cross_product(*this, a,src);
        if(res>0)
            return true;        //a极角较小
        else  if(res < 0)
            return false;    
        else  
            {
            
                res = (x-src.x)^2+(y-src.y)^2-(a.x-src.x)^2-(a.y-src.y)^2;
                if(res >0)    
                    return false;
                return true;
            }
    }
};
point point::src(0,0);
//计算向量和向量的叉乘,结果为正表示向量在向量的顺时针方向,反之
int cross_product(const point&  a,const point& b,const point& c)
{
    int res = (a.x - c.x)*(b.y - c.y)-(a.y - c.y)*(b.x - c.x);
    return res;
};
namespace std
{
    ostream & operator<<(ostream& out, const point &  p)
    {
        out<<"("<        return out;
    }
};
int main()
{
    vector p;
    point tmp;
    printf("请输入顶点坐标x,y\n");
    scanf("%d,%d",&tmp.x,&tmp.y);
    //输入(0,0)表结束
    while(tmp.x || tmp.y)
    {
        p.push_back(tmp);
        printf("请输入顶点坐标x,y\n");
        scanf("%d,%d",&tmp.x,&tmp.y);
    }
    cout<<"输入结束,所有顶点为："<    copy(p.begin(),p.end(),ostream_iterator(cout));
    cout<    
    //将最左下的点调整到p[0]的位置
    for(int i=1;i    {
        if(p[i].y            iter_swap(p.begin(),p.begin()+i);
    }
    point::src = p[0];
    sort(p.begin()+1,p.end());
    
    cout<<"排序之后,所有顶点为："<    copy(p.begin(),p.end(),ostream_iterator(cout," "));
    cout<    
    
    stack > s;
    //p[0]作为度量极角的原点，必定在最终的凸包中
    s.push(0);
    int i=1;
    while(i    {
        //说明p[i]为内点或多余的点（与p[i+1]的极角相同，而p[i+1]极径较大）,p[i]不用入栈，直接跳过
        while(i=0))
            i++;
        s.push(i); //顶点入栈
        i++;
    }
    cout<<"所求凸包如下(逆序):"<    while(!s.empty())
    {
        cout<        s.pop();
    }
    cout<    return 0;
}