Description
在xoy直角坐标平面上有n条直线L1,L2,…Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格
Sample Output
Solution
拿来笔和纸，手动模拟一下这个题，发现不管直线是什么，最后有贡献的直线一定会围成一个“V”形。然后这个V形从左向右，直线的斜率不断变大；还有一点很显然的是随着斜率的变大，两条直线交点横坐标也是不断变大的。
这对这道题有什么卵用呢？
由于这条性质，我们很容易就能用栈来维护V上的直线。先将直线按照斜率排序，每次新加入的直线和栈顶的比较即可。设栈为stack，共有tail条直线，那么如果新直线i与stack[tail]交点在stack[tail]与stack[tail-1]交点的左边（横坐标小），那么就弹出栈顶元素。直到交点在右边（横坐标大）或者栈中仅有一个元素，插入新直线即可。
（蒟蒻调这个题的时候，红字愣是没看见。。。WA了两次。。。QAQ）
Code
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
| #include <cstdio>
#include <algorithm>
const int maxn = 50009;
int n, id[maxn], H[maxn], tot = 0, sta[maxn];
double A[maxn], B[maxn], k[maxn], b[maxn];
bool cmp(int x, int y) { return A[x] == A[y] ? B[x] < B[y] : A[x] < A[y]; }
double calc(int i, int j) { return (b[j]-b[i]) / (k[i]-k[j]); }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lf%lf", A+i, B+i);
id[i] = i;
}
std::sort(id+1, id+n+1, cmp);
for (int j = 1; j < n; ++j) {
int i = id[j], ii = id[j+1];
if (A[i] != A[ii]) {
k[++tot] = A[i];
b[tot] = B[i];
H[tot] = i;
}
}
k[++tot] = A[id[n]];
b[tot] = B[id[n]];
H[tot] = id[n];
int tail = 0;
for (int i = 1; i <= tot; ++i) {
while (tail > 1 && calc(i, sta[tail]) <= calc(sta[tail], sta[tail-1]))
--tail;
sta[++tail] = i;
}
for (int i = 1; i <= tail; ++i) id[i] = H[sta[i]];
std::sort(id+1, id+tail+1);
printf("%d", id[1]); for (int i = 2; i <= tail; ++i) printf(" %d", id[i]);
}
|