HDU 2202 最大三角形（graham扫描法&&分治法凸包----又名快包）

http://acm.hdu.edu.cn/showproblem.php?pid=2202

这题先用凸包找出顶点，再暴力枚举

两种凸包

一：Graham扫描法：

(1)找出点集p[]中最左下的点p1，把p1同点集中其他各点用线段连接，并计算这些线段与水平线的夹角，然后按夹角从小到大和按到p1的距离从近到远排序(夹角范围为 [0, 180)度，而且可以删除相同夹角且距离p1较近的点，保留最远点，这样可减少计算量。因为直线上的非端点不是凸包的极点，即如果p1,p2,p3在一条直线上，则只取凸点p1,p3。p2不在端点，故可以去掉)，得到新的节点序列p1,p2,...pn.依次连接这些点，得到一个多边形(已经逆时针，有所进展，但还需去掉不在凸包上的点)。此时p1是凸包的边界起点，p2和pn也是最终凸包的顶点，p[n+1]=p1(看成循环的)

(2)删除p3,p4,...p[n-1]中不在凸包上的点：

先把p1,p2,p3入栈S中，再依次循环(i = 3 -> n-1)，若栈顶的两个点和当前的点p[i]这三点连线的方向向顺时针方向偏转，表明是凹的，应删除，则栈顶元素出栈(要循环判断，即可能前面的仍是凹的，还需再出栈，举例如下图)，直到向逆时针方向偏转或者栈内只有2个元素了(p1p2)，就把当前点p[i]入栈。

最后栈中的元素就是最终凸包上的点。

分析：一般会从最左下点p1开始，根据所有点斜率中最小的求下一个凸包点pa，再根据pa的所有点斜率中最小的来求下一个凸包点pb，依此类推，但这样就是三重循环(p1,pa,pb是一次，p1,pa,pb内部的排序有2次，共三重循环)，这样效率不高(其实这就是卷包裹法，复杂度为O(NH),其中N是全部的点数 H是最终在凸包上的点数)。Graham扫描法只取所有点对p1的斜率，后面的点充分利用该斜率的信息，并作某些处理，进行改进，以提高效率。这是由多到少，由多个到1个的方法，并充分利用已知条件。

ac代码：

#include<stdio.h>
#include<math.h>
typedef struct node
{
    double x,y;
    double angle;//记录该点相对第一个点的极角
}point;
point p[50010],stak[50010];
double angle(int i);
void Swap(int i,int j)//交换函数
{
    point temp;
    temp=p[j];
    p[j]=p[i];
    p[i]=temp;
}
double angle(int i)
{
    double x,y,m;
    x=p[i].x-p[0].x;
    y=p[i].y-p[0].y;
    m=sqrt(x*x+y*y);
    return -x/m;//这个函数算角度
}
int Loc(int top, int bot)
{
    double x = p[top].angle;
    int j, k;
    j = top+1;
    k = bot;
    while(1) {
        while(j < bot && p[j].angle < x) j++;
        while(k > top && p[k].angle > x) k--;

        if(j >= k) break;

        Swap(j, k);
    }
    Swap(top, k);
    return k;
}
void qsort(int top, int bot)
{
    //快排
    int pos;

    if(top < bot) {
        pos = Loc(top, bot);
        qsort(top, pos-1);
        qsort(pos+1, bot);
    }
}

//将大于中间的放到右边，小于的放到左边，返回中间位置
double cross_product(point a,point b,point c)//求叉乘，pa-pc,pb-pc,前者在后者顺时针方向时返回正数
{
    double x1,x2,y1,y2;
    x1=a.x-b.x;
    y1=a.y-b.y;
    x2=b.x-c.x;
    y2=b.y-c.y;
    return (x1*y2-x2*y1);
}
double maxx(double a,double b)
{
    return a>b?a:b;
}
double area(point a,point b,point c)
{
    double x1,x2,y1,y2;
    x1=a.x-c.x;
    y1=a.y-c.y;
    x2=b.x-c.x;
    y2=b.y-c.y;
    return fabs(x1*y2-x2*y1)/2;
}
double answer(int top)
{
    int i,j,k;
    double ans=-999999;
    /*for(i=0;i<top;i++)
        printf("x=%lf y=%lf\n",stak[i].x,stak[i].y);*/
    for(i=0;i<top;i++)
        for(j=i+1;j<top;j++)
           for(k=j+1;k<top;k++)
            ans=maxx(ans,area(stak[i],stak[j],stak[k]));
    return ans;
}
double distance(point a,point b)//算出两点距离
{
    return sqrt(pow(a.x-b.x,2.0)+pow(a.y-b.y,2.0));
}
int graham(int n)//graham扫描法
{
    int i,j,k,top;
    double temp;
    stak[0]=p[0];stak[1]=p[1];stak[2]=p[2];
    top=2;//前三个元素入栈
    for(i=3;i<n;i++)
    {
        while(cross_product(p[i],stak[top],stak[top-1])>0&&top>=1)top--;//由次栈顶元素，栈顶元素和pi形成角不是向左转的元素都出栈
            stak[++top]=p[i];//将pi入栈
    }
    return (top+1);
}
int main()
{
    int n,i,flag;
    double Miny,Minx;
    while(scanf("%d",&n)!=EOF)
    {
        Minx=Miny=9999999;
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
            if(Miny>p[i].y)
            {
                Minx=p[i].x;
                Miny=p[i].y;
                flag=i;
            }
            else if(Miny==p[i].y)
                if(Minx>p[i].x)
                {
                    Minx=p[i].x;
                    flag=i;
                }
        }
        Swap(flag,0);
        p[0].angle=0;
        for(i=1;i<n;i++)
            p[i].angle=angle(i);
        qsort(1,n-1);//按与x轴夹角从小到大排序
        //for(i=0;i<n;i++)
           // printf("x=%.0lf y=%.0lf,angle=%lf\n",p[i].x,p[i].y,p[i].angle);
        i=graham(n);
        //printf("top=%d\n",i);
        printf("%.2lf\n",answer(i));
    }
    return 0;
}      

View Code

感谢@Thirteen_9提示，根据cos图像可得，这是条递减曲线，只需把它取反即可得到相同效果，不必acos

上面代码中，resultList为全局变量，是最终凸包顶点集合，而leftList、rightList是局部变量。而且dealwith()函数中的insert(resultList,side,node)这个插入函数，是在边的起点和中点之间插入。例如上图15-9中，在边p1、pn之间插入pmax，下次在p1、pmax之间插入s11中的凸点，这样是满足最终凸包的顺序的。

ac代码

/*
 分治凸包
 顺时针！！！！
 */
 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<math.h>
 typedef struct node{
     double x,y;
 }point;
point stak [50005],p[50005];
int cmp(const void *a,const void *b)
{
    point *pa=(point *)a;
    point *pb=(point *)b;
    if(pa->y==pb->y)
        return pa->x-pb->x;
    else return pa->y-pb->y;
}
int mult( point a,point b,point c )//求叉积
{
     return (a.x - c.x) * (b.y - c.y)-(b.x - c.x) * (a.y - c.y);
}
 int quickhull( int n )
 {
     int i, len, k = 0;
     int top = 1;
     qsort(p,n,sizeof(p[0]),cmp);
     if (n == 0) return 0; stak[0] = p[0],top=0;
     if (n == 1) return 1; stak[1] = p[1],top=1;
     if (n == 2) return 2; stak[2] = p[2],top=2;
     for (i = 2; i < n; i++) {//前两个点要初始化入栈
         while (top && mult(stak[ top ], p[ i ], stak[top-1])>=0 )//( cross ： from top to i )如果左拐栈顶元素就出栈
             top--;
         stak[++top] = p[i];
     }
     len = top; stak[++top] = p[n - 2];
     for (i = n - 3; i >= 0; i--) {//这里i从n-3开始循环，跟上面同理
         while (top!=len && mult(stak[ top ], p[ i ], stak[top-1])>=0 )
         top--;
         stak[++top] = p[i];
     }
     return top; // 返回凸包中点的个数
 }
 double maxx(double a,double b)
 {
     return a>b?a:b;
 }
 int main(){
     int n;
     int i,j,k,top;
     double ans,temp;
     while( scanf("%d",&n)!=EOF ){
         for( i=0;i<n;i++ )
             scanf("%lf%lf",&p[i].x,&p[i].y);
        top=quickhull( n );
         ans=0;
        /* for(i=0;i<top;i++)
            printf("x=%lf y=%lf\n",stak[i].x,stak[i].y);*/
         for( i=0;i<top;i++ ){
             for( j=i+1;j<top;j++ ){
                 for( k=j+1;k<top;k++ ){
                    temp=fabs(mult(stak[i],stak[k],stak[j]));
                    ans=maxx(ans,temp);
                 }
             }
         }
         ans*=0.5;
         printf("%.2lf\n",ans);
     }
     return 0;
 }      

View Code

转载于:https://www.cnblogs.com/huzhenbo113/p/3277853.html