「Bzoj 1007」「HNOI2008」水平可见直线 (计算几何+单调栈)

发表于 | 分类于 | | + s

BZOJ 1007
其实是求一个半凸包(从左到右依次观察每条边和每个顶点，发现其斜率不断增大，顶点的横坐标也不断增大)，我们把直线按斜率$k$从小到大排，$k$一样$b$从大到小排。只处理$b$最大的那条直线，因为这样和之前的直线交点尽可能右。

我们维护一个单调栈$S$，如果当前直线i能完全覆盖栈顶直线$S_{top}$，则$i$与$S_{top}$的交点一定在$S_{top}$与$S_{top-1}$的交点左边或者重合。若在它左边或者重合，则弹出栈顶，直到交点在右边后，扔进栈里。最后栈中元素就是答案。

程序实现时，不直接放两个直线不用复杂判斜率相同！

2019.1.5 重打：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 50000 + 5;
    const db eps = 1e-8;

    struct data {
        int k, b, id;
        bool operator < (const data &rhs) const {
            return (k == rhs.k) ? b > rhs.b : k < rhs.k;
        }
    }zx[MAXN];

    db getCross(int a, int b) {
        return 1.0 * (zx[b].b - zx[a].b) / (zx[a].k - zx[b].k);
    }

    int n, top, s[MAXN], ans[MAXN];

    void clean() {
        top = 0;
        ms(ans, 0);
    }
    int solve() {
        clean();
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d%d", &zx[i].k, &zx[i].b), zx[i].id = i;
        sort(zx + 1, zx + 1 + n);
        s[++top] = 1; // 不直接放两个直线不用复杂判斜率 
        for (int i = 2; i <= n; ++i) {
            if (fabs(zx[i].k - zx[i - 1].k) < eps) continue ;
            if (top <= 1) {s[++top] = i; continue ;} // 不直接放两个要特判 
            while ((top > 1 && getCross(s[top], s[top - 1]) - getCross(s[top], i) > -eps)) --top;
            s[++top] = i;
        }
        for (int i = 1; i <= top; ++i) ans[zx[s[i]].id] = 1;
        for (int i = 1; i <= n; ++i) if (ans[i]) printf("%d ", i);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 50000 + 5;
const db eps = 1e-8; 
int abss(int x) {return x > 0 ? x : -x;}
struct data {
    int k, b, id;
    bool operator < (const data &y) const {
        if (k == y.k) return b > y.b; 
        return k < y.k;
    }
}e[MAXN];
db getXPos(int a, int b) {
    return (db)(e[b].b - e[a].b) / (db)(e[a].k - e[b].k);
}
int n, top = 0, s[MAXN], ans[MAXN];
void clean() {
    top = 0, ms(s, 0), ms(ans, 0);
}
void solve() {
    clean(); 
    for (int i=1;i<=n;i++) scanf("%d%d", &e[i].k, &e[i].b), e[i].id = i;
    sort(e + 1, e + 1 + n);
    s[++top] = 1;
    for (int i=2;i<=n;i++) {
        if (fabs(e[i].k - e[i - 1].k) < eps) continue;
        while (top > 1 && getXPos(i, s[top]) <= getXPos(s[top], s[top - 1])) top--;
        s[++top] = i;
    }
    while (top) ans[e[s[top--]].id] = 1;
    for (int i=1;i<=n;i++) if (ans[i]) printf("%d ", i);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d", &n), solve();
    return 0;
}
------ 本文结束 ------