[HDU]2202最大三角形、3934Summer holiday

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

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

在n个点中找出3个点，使得面积最大。

这题用到的就是葛立恒扫描法。

葛立恒扫描法是什么呢？现将现有的所有点进行排序，y从小到大。x从小到大。

这样的话，我们可以得到什么呢？首先，y最小，x最小的一定是凸包点，这一点没有疑义吧。同理，x最大，y最大的也肯定是凸包点，我们所采用的步进法也将以这两个点作为开始。

步进法分为两部分，我们姑且叫第一部分为左链，第二部分为右链。

我们从左链开始，首先，取出0，1，2点。（至少需要3点才能比较，0是最小的点，上述已证明肯定是凸包点），假如0→2，斜率大于0→1，所以1肯定不是凸包点，舍去，接着0，2，3假如0→3，斜率大于0→2，那2也肯定不是凸包点，舍去。接下来重复此步骤。直至点n。（ps：上述斜率的比较用叉乘来进行，即叉乘结果为正的话，向左转，从而证明斜率大小）假如中间出现了y轴相等，x轴不等的点，这点暂时存入。（因为假设这个点最外围的，那这条线段的两个点都是凸包点。）如果接下来有斜率比这两条大的线的话，很明显，这两个点也要舍去。

这样就判断完了左链，右链同理，不过起始点是从最大点开始。

#include"stdio.h"
#include"stdlib.h"
#include"math.h"
struct Point
{
    int x;
    int y;
};
Point p[100010];
int n;
int cmp(const void *a,const void *b)     //判断快排时，摆放的位置，即x，y从小到大， 
{
    Point *c =(Point *)a;
    Point *d =(Point *)b;
    if(c->y==d->y)
        return c->x-d->x;
    else
        return c->y-d->y;
}
int cross(Point p1,Point p2,Point p3)         //叉乘 
{
    return (p3.x-p2.x)*(p1.y-p2.y)-(p3.y-p2.y)*(p1.x-p2.x);
}
int convex(int s[])
{
    int i,m,m1; 
    for(m=0,i=0;i<n;i++){           //左链 
        while(m>1 && cross(p[s[m-2]],p[s[m-1]],p[i])>=0)
            m--;
        s[m++]=i;
    }
    m1=m;
    for(i=n-2;i>0;i--){             //右链 
        while(m>m1 && cross(p[s[m-2]],p[s[m-1]],p[i])>=0)
            m--;
        s[m++]=i;
    }
    return m;
}
double area(int i,int j,int k)
{
    double s=fabs(double(p[i].x*p[j].y+p[j].x*p[k].y+p[k].x*p[i].y-p[i].y*p[j].x-p[j].y*p[k].x-p[k].y*p[i].x)/2);    
    return s;
}
int main()
{
    int s[100010];
    double max,temp;
    int i,j,k,m;
    while(scanf("%d",&n)!=EOF)
    {
        
        for(i=0;i<n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        qsort(p,n,sizeof(p[0]),cmp);
        m=convex(s);
        max=0;
        for(i=0;i<m-2;i++)
         for(j=i+1;j<m-1;j++)
          for(k=j+1;k<m;k++)
           {
              temp=area(s[i],s[j],s[k]);
              max=max>temp?max:temp;
           }
        printf("%.2lf\n",max);
    }
    return 0;
}

[HDU]2202最大三角形、3934Summer holiday

推荐阅读