注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj1007  

2013-01-23 12:38:51|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

水平可见直线:

听说是半平面交于是我特地放下BZOJ去学习半平面交然后看题解发现不用半平面交

其实就是按斜率排序,也就是按极角排序之后,用一个栈乱搞一下。

如果i直线与i-1直线平行,取上面的那个

否则跟栈顶、栈顶的下一条直线比较。假设当前直线是now,栈顶是stack[top]

求出now与stack[top]的交点P,stack[top]与stack[top-1]的交点Q。由于已排好序所以now的斜率大于stack[top]的斜率大于stack[top-1]的斜率

画个图可以发现P左边now在stack[top]上方,Q右边stack[top-1]在stack[top]上方。那么如果P在Q右边就看不到stack[top]了,然后退栈。

可是我很傻逼的为一个问题纠结了好久那就是如果是一条竖直向上的直线这个结论不成立啊啊!

然后发现这种直线根本不能用y=kx+b表示……囧

由于前后思路不连贯所以程序中有不需要的语句,这是因为之前写了后来发现之前的理解是错误的,结果忘记删了。大家看着办吧


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 50010
#define eps 1e-10
#define pi 3.1415926535897932384626
using namespace std;
int dcmp(double p)
{
    if(fabs(p)<eps)return 0;
    return p>eps?1:-1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double a,double b):x(a),y(b){}
    friend Point operator + (const Point &a,const Point &b){  return Point(a.x+b.x,a.y+b.y);  }
    friend Point operator - (const Point &a,const Point &b){  return Point(a.x-b.x,a.y-b.y);  }
    friend Point operator * (const Point &a,double b){  return Point(a.x*b,a.y*b);  }
};
typedef Point Vector;
struct Line
{
    Point P;
    Vector v;
    double rad;
    int num;
    Line(){}
    Line(const Point &a,const Vector &v,int num):P(a),v(v),num(num){  rad=atan2(v.y,v.x);  }
    friend bool operator < (const Line &a,const Line &b){  return a.rad<b.rad;  }
}L[MAXN];
double Cross(const Vector &a,const Vector &b){  return a.x*b.y-a.y*b.x;  }
double interx(Line a,Line b)
{
    Vector v=a.P-b.P;
    double t=Cross(b.v,v)/Cross(a.v,b.v);
    Point ans=a.P+a.v*t;
    return ans.x;
}
int n,stack[MAXN],top,ans[MAXN],tot;
void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        double k,b;
        scanf("%lf%lf",&k,&b);
        L[i]=Line(Point(0,b),Vector(1,k),i);
    }
}
void solve()
{
    sort(L+1,L+n+1);
    for(int i=1;i<=n;i++)
    {
        if(top>=1&&!dcmp(Cross(L[stack[top]].v,L[i].v))&&L[i].P.y<L[stack[top]].P.y)  continue;
        while(top>=1&&!dcmp(Cross(L[stack[top]].v,L[i].v)))  top--;
        while(top>1&&dcmp(interx(L[i],L[stack[top]])-interx(L[stack[top]],L[stack[top-1]]))<=0)  top--;
        stack[++top]=i;
    }
}
void print()
{
    for(int i=1;i<=top;i++)
        ans[++tot]=L[stack[i]].num;
    sort(ans+1,ans+tot+1);
    for(int i=1;i<=tot;i++)
        printf("%d ",ans[i]);
    printf("\n");
}
int main()
{
    read();
    solve();
    print();
    return 0;
}


  评论这张
 
阅读(426)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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