首页 > 代码库 > BZOJ 1007 HNOI2008 水平可见直线 半平面交
BZOJ 1007 HNOI2008 水平可见直线 半平面交
题目大意:给定n条直线,求从上到下俯瞰能看到哪些直线
半平面交的裸题
首先将所有直线按照斜率排序,依次入栈
如果一条直线和栈顶的交点在栈顶直线和栈顶下面那条直线的交点的左侧,则删除栈顶
若多条直线斜率相同,只插入截距最大的那条直线
最后记录答案输出即可
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 50500 using namespace std; typedef pair<double,double> point; struct line{ double k,b; int pos; bool operator < (const line &y) const { if( fabs(k-y.k) < 1e-7 ) return b < y.b; return k < y.k; } }lines[M]; int n,top; line *stack[M]; bool ans[M]; point Cross(const line &l1,const line &l2) { double x=(l1.b-l2.b)/(l2.k-l1.k); double y=l1.k*x+l1.b; return point(x,y); } void Insert(line &l) { while(top>1) { point p1=Cross(l,*stack[top]); point p2=Cross(*stack[top],*stack[top-1]); if( p1.first-p2.first<1e-7 ) stack[top--]=0x0; else break; } stack[++top]=&l; } int main() { int i; cin>>n; for(i=1;i<=n;i++) scanf("%lf%lf",&lines[i].k,&lines[i].b),lines[i].pos=i; sort(lines+1,lines+n+1); for(i=1;i<=n;i++) if( i==n || fabs(lines[i].k-lines[i+1].k)>1e-7 ) Insert(lines[i]); while(top) ans[stack[top--]->pos]=1; for(i=1;i<=n;i++) if(ans[i]) printf("%d ",i); }
BZOJ 1007 HNOI2008 水平可见直线 半平面交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。