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

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;
}
------ 本文结束 ------