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