注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2079 Triangle 凸包+旋转卡壳 求最大三角形面积  

2011-04-18 11:45:40|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给定一组点集,选择三点组成三角形,且面积最大。
肯定要求出这组点的凸包,接下来就不能想当然的三重循环枚举三点,这样很容易超时。这时就要用到神奇的旋转卡壳法。
取凸包的三点i,j,k。先固定i,j。逆时针(当然你也可以顺时针)变换k,你会发现i,j,k三点组成的三角形面积具有单峰性。即如果第一次找到Area(i,j,k+1)<Area(i,j,k),那么此时就是在i,j固定下的形成最大面积的k点了。这样两重循环枚举i,j,时间复杂度为o(n^2)。也许有人会认为不是也要找k吗?时间复杂度为(n^3)才对。非也,如果你认真观察的话,你会发现在枚举j时,k并不需要从初始枚举,因为j在逆时针移动时,k也在逆时针移动。所以只需从上一个k开始接着逆时针找k。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point   
{
    double x,y;
};
bool mult(Point curr, Point end, Point begin)
{
    return (curr.x-begin.x)*(end.y-begin.y)
    >=(end.x-begin.x)*(curr.y-begin.y);
}
bool comp(const Point &a,const Point &b)
{
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
int graham(Point pnt[], int n, Point res[])
{
    int i,len,top=1;
    sort(pnt,pnt+n,comp);
    if(n==0)
    {
        return 0;
    }
    res[0]=pnt[0];
    if(n==1)
    {
        return 1;
    }
    res[1]=pnt[1];
    if(n==2)
    {
        return 2;
    }
    res[2]=pnt[2];
    for(i=2;i<n;i++)
    {
        while(top&&mult(pnt[i],res[top],res[top-1]))
        {
            top--;
        }
        res[++top]=pnt[i];
    }
    len=top;
    res[++top]=pnt[n-2];
    for(i=n-3;i>=0;i--)
    {
        while(len!=top&&mult(pnt[i],res[top],res[top-1]))
        {
            top--;
        }         
        res[++top]=pnt[i];
    }
    return top;
}
double Area(Point a,Point b,Point c)
{
    return fabs((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y))/2;
}
int main()
{    
    int n;
    Point s[50005],res[50005];
    while(scanf("%d",&n)==1&&n>0)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&s[i].x,&s[i].y);
        }
        int m=graham(s,n,res);
        double ans=0;
        int p1,p2,p3;
        for(p1=0;p1<m;p1++)
        {
            p2=(p1+1)%m;
            p3=(p2+1)%m;
            ans=max(ans,Area(res[p1],res[p2],res[p3]));
            while(Area(res[p1],res[p2],res[(p3+1)%m])>Area(res[p1],res[p2],res[p3]))
            {
                //ans=max(ans,Area(res[p1],res[p2],res[p3+1]));
                p3=(p3+1)%m;
            }
            while((p1-p3+m)%m>1)
            {
                ans=max(ans,Area(res[p1],res[p2],res[p3]));
                while(Area(res[p1],res[p2],res[(p3+1)%m])>Area(res[p1],res[p2],res[p3]))
                {
                    //ans=max(ans,Area(res[p1],res[p2],res[p3+1]));
                    p3=(p3+1)%m;
                }
                p2=(p2+1)%m;
                //ans=max(ans,Area(res[p1],res[p2],res[p3]));
            }
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}
  评论这张
 
阅读(636)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018