【BZOJ1007】水平可见直线（单调栈）

题解

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

题解

首先，如果斜率相同，显然只需要留下截距大的直线

去掉没有用的直线之后

剩余直线按照斜率从小到大排序

用一个单调栈来维护每条直线

如果当前新加的直线与top的交点在top-1的交点的左侧

证明这条直线可以被完全覆盖

然后就不难了

#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;

}