[BZOJ1007] horizontal visible straight line (monotone stack)

Title Solution

Description

There are n lines L1,L2 Ln, if you look down at the place where y is positive infinity and you can see some sub line segment of Li, then Li is
Visible, otherwise Li is covered
For example, for a line:
L1:y=x; L2:y=-x; L3:y=0
Then L1 and L2 are visible and L3 is covered
n straight lines are given, which are expressed in the form of y=Ax+B (|a|, |b| < = 500000), and n straight lines do not coincide with each other. All visible straight lines are obtained

Input

The first line is n (0 < n < 50000), and the next N lines are Ai,Bi

Output

Output the number of visible lines from small to large, separated by spaces between the two, and there must be a space after the last number

Sample Input

3

-1 0

1 0

0 0

Sample Output

1 2

Title Solution

First of all, if the slopes are the same, it's obvious that you only need to leave a straight line with a large intercept
After removing useless lines
The remaining lines are sorted by slope from small to large
Maintain each line with a monotone stack
If the intersection of the newly added line and top is to the left of the intersection of top-1
Prove that this line can be completely covered
And then it's not hard

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 55000
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,tot;
struct Line{int a,b,id;}e[MAX];
bool cmp(Line a,Line b){if(a.a!=b.a)return a.a<b.a;return a.b>b.b;}
double ppp(int x,int y){return 1.0*(e[y].b-e[x].b)/(e[x].a-e[y].a);}
int S[MAX],ans[MAX],top=0;
int main()
{
    n=read();
    for(int i=1;i<=n;++i)e[i].a=read(),e[i].b=read(),e[i].id=i;
    sort(&e[1],&e[n+1],cmp);
    e[0].a=-1e9;
    for(int i=1;i<=n;++i)if(e[i].a!=e[i-1].a)e[++tot]=e[i];
    n=tot;
    S[++top]=1;ans[top]=e[1].id;
    for(int i=2;i<=n;++i)
    {
        while(top>1&&ppp(i,S[top-1])>=ppp(i,S[top]))top--;
        S[++top]=i;ans[top]=e[i].id;
    }
    sort(&ans[1],&ans[top+1]);
    for(int i=1;i<=top;++i)printf("%d ",ans[i]);puts("");
    return 0;
}

Posted on Fri, 01 May 2020 11:40:38 -0700 by dean7