[算法课][分治]寻找凸包（ConvexHull）

#include 
#include 
#include 
#define N 100
using namespace std;

int n=0;
struct POINT
{
    int x,y;
}p[N],ans[N];
int visit[N],mark[N];
int Djudge(POINT a1,POINT a2,POINT a3)
{
    int calculate=a1.x*a2.y+a3.x*a1.y-a3.x*a2.y-a2.x*a1.y-a1.x*a3.y;
    return calculate;
}
bool cmpxy(const POINT a,const POINT b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}

/*在涉及到平面上点对问题时，经常会按照这种方法对点进行排序
这与后面的sort(p,p+n,cmpxy)经常一起使用，在最近我做的2D maximal finding problem时，也是
使用了这样的排序对点对进行预处理。
*/
void DealLeft(int first,int last)
{
    int max=0,index=-1;
    int i=first;
    if(first<last)
    {
        for(i=first+1;i)
        {
            int calcu=Djudge(p[first],p[i],p[last]);
            if(calcu==0)
                visit[i]=1;
            if(calcu>max)
            {
                max=calcu;
                index=i;
            }
        }
    }
    else
    {
        for(i-1;i>last;i--)
        {
            int calcu=Djudge(p[first],p[i],p[last]);
            if(calcu==0)
                visit[i]=1;
            if(calcu>max)
            {
                max=calcu;
                index=i;
            }
        }
    }
    if(index!=-1)
    {
        visit[index]=1;
        DealLeft(first,index);
        DealLeft(index,last);
    }
}
int main()
{
    cout<<"Enter the number of the points: ";
    cin>>n;
    cout<<"Enter the points: ";
    for(int i=0;i)
    {
        cin>>p[i].x>>p[i].y;
        visit[i]=0;
    }
    visit[0]=1;
    visit[n-1]=1;
    sort(p,p+n,cmpxy);
    DealLeft(0,n-1);
    DealLeft(n-1,0);
    int t=0;
    for(int i=0;i)
    {
        if(visit[i]==1)
        {
            ans[t].x==p[i].x;
            ans[t].y==p[i].y;
            t++;
        }
    }
//顺时针输出
    mark[0]=mark[t-1]=1;
    for(int i=1;i1;i++)
        mark[i]-0;
    cout<0].x<<" "<0].y<<endl;
    for(int i=1;i1;i++)
    {
        int d=Djudge(ans[0],ans[t-1],ans[i]);
        if(d>=0)
        {
            cout<" "<endl;
            mark[i]=1;
        }
    }
    cout<1].x<<" "<1].y<<endl;
    for(int i=1;i)
    {
        if(mark[i]!=1)
        {
            int d=Djudge(ans[0],ans[t-1],ans[i]);
            if(d<0)
            {
                cout<" "<endl;
            }
        }
    }
    return 0;
}