【BZOJ1007】【HNOI2008】水平可见直线（斜率排序+单调栈）

2022-07-21 15:03:16

1007: [HNOI2008]水平可见直线

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2605 Solved: 914
[Submit][Status]

Description

Input

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

Output

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

Sample Input

3
-1 0
1 0
0 0

Sample Output

1 2

HINT

Source

分析：本蒟残还是太弱，只能膜拜题解：

以下摘自wyl大神的空间：http://hi.baidu.com/wyl8899/item/061d3b0de2c42b344bc4a362

正解是按斜率排序，用栈维护可见直线。

如右图，当前考虑直线now，栈顶top，栈顶的下一个元素top'大致的位置。

显然now和top'将把top完全遮盖。

思考一下可以得出，记两直线交点的横坐标为x(A,B)，则x(now,top)<=x(top,top')时，栈顶直线被废，弹出栈。

反复这样操作，直至不满足上面的条件，将当前直线压入栈中。

最后在栈中的直线就是答案。

对了，同斜率的直线，显然只考虑截距最大的那个就好了，因此要处理一下(当然不处理的话x(now,top)的计算过程中要divided by 0)

总结：一般情况下处理多条直线的问题都是将它们按照斜率排序（我发现很多直线题这一步都是基础），而且之后就能用单调性维护（这个也经常见到，比如斜率优化dp里面就是用单调队列，本题用单调栈）

code：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn=;

 struct wjmzbmr

 {

     int k,b,w;

     bool operator < (const wjmzbmr& x) const

     {

         return (k<x.k)||((k==x.k)&&(b>x.b));

     }

 }a[maxn+];

 wjmzbmr c[maxn+];

 int n,stack[maxn+],b[maxn+];

 bool f[maxn+];

 bool pd(int now,int top,int ltop)

 {

     double x1=(double)(c[top].b-c[now].b)/(double)(c[now].k-c[top].k);

     double x2=(double)(c[top].b-c[ltop].b)/(double)(c[ltop].k-c[top].k);

     if(x2-x1>=0.0) return true;else return false;

 }

 int main()

 {

     freopen("ce.in","r",stdin);

     freopen("ce.out","w",stdout);

     scanf("%d",&n);

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

     {

         scanf("%d%d",&a[i].k,&a[i].b);

         a[i].w=i;

         c[i]=a[i];

     }

     sort(a,a+n);

     int size=;b[size]=a[].w;

     for(int i=;i<n;++i) if(a[i].k!=a[i-].k) b[++size]=a[i].w;

     int len=;

     memset(stack,,sizeof(stack));

     stack[]=b[],stack[]=b[];

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

     {

         while(len>=&&pd(b[i],stack[len],stack[len-])) --len;

         stack[++len]=b[i];

     }

     memset(f,,sizeof(f));

     for(int i=;i<=len;++i) f[stack[i]]=;

     for(int i=;i<n;++i) if(f[i]==) printf("%d ",i+);

     return ;

 }

码农公寓