BZOJ 1007 水平可见直线

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条直线两两不重合.求出所有可见的直线.

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input

3
-1 0
1 0
0 0

Sample Output

1 2

HINT

Source

两种做法吧：

直接半平面交暴搞，虽然我不会写；
第二种主要是针对这个题目的：利用题所隐藏的性质。稍微YY一下，所能看到的直线沿着X正方向斜率一定是单调递增的。

　　首先将斜率排序(从小到大)之后一次加入栈中。对于栈顶直线l1,次顶直线l2，以及所枚举到的直线i,如果l与l1的交点在l1与l2交点左方，栈顶的弹出(证明：画画图就知道了)。

　　最后栈中的直线即为答案。(这个好像就是半平面交)

代码如下：

 1 #include<cstdlib>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 #define esp (1e-6)
 8 #define maxn 50010
 9 int n,S[maxn],top;
10 vector <int> vec;
11 struct Line{double A,B; int ord;}line[maxn];
12 
13 inline bool cmp(Line a,Line b)
14 {
15     if (a.A == b.A) return a.B > b.B;
16     return a.A < b.A;
17 }
18 
19 inline double calc(Line a,Line b) {return (double)(b.B-a.B)/(double)(a.A-b.A);}
20 
21 inline bool okay(double a,double b)
22 {
23     if (a + esp > b &&a-esp<b) return true;
24     if (a > b) return true;
25     return false;
26 }
27 
28 inline void work()
29 {
30     int i;
31     S[++top] = 1; i = 2;
32     while (i <= n&&line[i].A == line[i-1].A) i++;
33     if (i <= n)
34     {
35         S[++top] = i; ++i;
36         while (i <= n&&line[i].A == line[i-1].A) i++;
37         for (;i <= n;++i)
38         {
39             if (line[S[top]].A == line[i].A)
40                 continue;
41             else
42             {
43                 while (top > 1 && okay(calc(line[S[top]],line[S[top-1]]),calc(line[S[top]],line[i])))
44                     --top;
45                 S[++top] = i;
46             }
47         }
48     }
49     for (i = 1;i <= top;++i) vec.push_back(line[S[i]].ord);
50     sort(vec.begin(),vec.end());
51 }
52 
53 int main()
54 {
55     freopen("1007.in","r",stdin);
56     freopen("1007.out","w",stdout);
57     scanf("%d",&n); int i;
58     for (i = 1;i <= n;++i)
59     {
60         scanf("%lf %lf",&line[i].A,&line[i].B);
61         line[i].ord = i;
62     }
63     sort(line+1,line+n+1,cmp);
64     work();
65     int nn = vec.size();
66     for (i = 0;i < nn;++i) printf("%d ",vec[i]);
67     fclose(stdin); fclose(stdout);
68     return 0;
69 }

View Code