水平可见直线 bzoj 1007

水平可见直线

【问题描述】

在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

【输出格式】

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

【样例输入】

-1 0

1 0

0 0

【样例输出】

1 2

题解：

1.对于斜率相同的两条直线截距小的被覆盖。

2.对于斜率不同的三条直线，如果一条直线不可见

那么必定是斜率最大和斜率最小的覆盖另外一条线段

同时斜率最大和斜率最小的直线的交点在另一条线段的上方

根据这个性质，通过排序和单调栈即可维护可见直线。

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 inline int Get()

 {

     int x = , s = ;

     char c = getchar();

     while('' > c || c > '')

     {

         if(c == '-') s = -;

         c = getchar();

     }

     while('' <= c && c <= '')

     {

         x = (x << ) + (x << ) + c - '';

         c = getchar();

     }

     return x * s;

 }

 int n;

 struct shape

 {

     int a, b, i;

 };

 shape a[];

 int s[];

 int ans[];

 inline bool rule(shape a, shape b)

 {

     if(a.a != b.a) return a.a > b.a;

     return a.b > b.b;

 }

 inline double Sol(int x, int y)

 {

     return (double) (a[y].b - a[x].b) / (double) (a[x].a - a[y].a);

 }

 int main()

 {

     n = Get();

     for(int i = ; i <= n; ++i)

     {

         a[i].a = Get();

         a[i].b = Get();

         a[i].i = i;

     }

     sort(a + , a +  + n, rule);

     int top = ;

     for(int i = ; i <= n; ++i)

     {

         if(a[i].a == a[s[top]].a) continue;

         while(top >  && Sol(s[top], i) >= Sol(s[top], s[top - ]))

             --top;

         s[++top] = i;

         ans[top] = a[i].i;

     }

     sort(ans + , ans +  + top);

     for(int i = ; i <= top; ++i) printf("%d ", ans[i]);

 }

巴特西

水平可见直线 bzoj 1007

最新文章

热门文章