[bzoj1007]：[HNOI2008]水平可见直线（单调栈）

本文主要是介绍[bzoj1007]：[HNOI2008]水平可见直线（单调栈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
姑且算是计算几何第一题吧。。
首先，最后的图形一定是一个凸包形状的东西。
所以，我们按照k递增为第一关键字，b递减为第二关键字，排个序。
然后我们就可以维护一个单调栈，处理结果了。
方法：
我们设当前直线与栈顶直线的交点为x1，栈顶直线与栈顶第二条直线的交点为x2
如果x1<=x2，那么弹出栈顶；否则将当前直线压入栈中。
原理可以看这个图，直到看懂为止。

懂了的话，那就没什么了。
对了，目前洛谷Rank1
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=5e5+5;
const double eps=1e-8;
struct line{double k,b;int id;inline bool operator < (const line& y) const {if(fabs(k-y.k)<eps)return b>y.b;return k<y.k;}
}a[N];
int n,top,vis[N],s[N];
inline double calc(const line& a,const line& b){return (b.b-a.b)/(a.k-b.k);
}
int main(){n=read();for(int i=1;i<=n;i++)scanf("%lf %lf",&a[i].k,&a[i].b),a[i].id=i;sort(a+1,a+n+1);top=1;s[1]=1;for(int i=2;i<=n;i++){if(fabs(a[i].k-a[i-1].k)<eps)continue;while(top>1&&calc(a[i],a[s[top]])<=calc(a[s[top]],a[s[top-1]])+eps)top--;s[++top]=i;}for(int i=1;i<=top;i++)vis[a[s[i]].id]=1;for(int i=1;i<=n;i++)if(vis[i])printf("%d ",i);return 0;
}

这篇关于[bzoj1007]：[HNOI2008]水平可见直线（单调栈）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---