BZOJ 1007: [HNOI2008]水平可见直线 – [单调栈]


题目传送门(BZOJ)
>原文链接<

题解 :

如果会了斜率优化, 这道题做起来很简单.

首先把所有直线按斜率排序, 斜率大的肯定不会被斜率小的盖上, 如果斜率一样, 按截距排序.

然后按这个顺序一条一条把直线入栈,

若后来的直线斜率和栈顶斜率一样, 那么栈顶必定没有用, 弹出(因为截距小)

若栈顶和第二栈顶的交点在这条线和栈顶的交点右侧, 那么栈顶必然没用, 弹出 (因为这条直线和第二栈顶完全覆盖了栈顶)

就这么一条一条插, 最后统计答案, 代码实现简单, 如果弹出部分不是很懂, 可以看看代码

代码 :

#include 
#include 
#include 
#include 
#define f2 double
const int N = 51000;
const f2 eps = 1e-6;
using namespace std;
struct Node {
    f2 a, b;
    int idx;
    bool operator < (const Node &A) const {
        return fabs(a-A.a) < eps ? b < A.b : a < A.a;
    }
}a[N], s[N];
bool ans[N];
int top, n;
f2 calc(const Node &x1, const Node &x2) {
    return (x2.b-x1.b)/(x1.a-x2.a);
}
void insert(Node a) {
    while(top) {
        if(fabs(s[top].a-a.a) < eps)top--;
        else if(top > 1 && calc(a, s[top-1]) <= calc(s[top], s[top-1])) top--;
        else break;
    }
    s[++top]=a;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%lf%lf", &a[i].a, &a[i].b);
        a[i].idx = i;
    }
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; i ++ ) insert(a[i]);
    for(int i = 1;i <= top; i ++ ) ans[s[i].idx] = 1;
    for(int i = 1; i <= n; i ++ ) if(ans[i]) printf("%d ",i);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注