Bzoj 1007(计算几何+单调栈)

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}

------ 本文结束 ------