bzoj 1007: [HNOI2008]水平可见直线（模拟栈）

http://www.lydsy.com/JudgeOnline/problem.php?id=1007

1007: [HNOI2008]水平可见直线

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 7644  Solved: 2922

[Submit][Status][Discuss]

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

【解析】：

用数组模拟栈，先按斜率排序。

其实最后看到的是一个碗，所以，斜率是递增的，如果存在斜率相等的，在下方的直接舍去。

交点的x坐标也是递增的。

所以，如果当前加入的直线，与栈顶直线的交点x<栈顶与栈中第二直线交点x，则覆盖上一条直线

否则，这条直线加入栈

最后把栈中的直线编号按顺序输出即可。

【代码】：

#include <stdio.h>
#include <stdlib.h>  
#include <string.h>  
#include <algorithm> 
using namespace std;
struct line{//存直线
	double a,b;
	int dex;
}l[52020],s[52020];//l存直线，s模拟栈 
int n,ans[52020];
bool cmp(line l1,line l2)//按斜率从小到大排序
{
	if(l1.a==l2.a)return l1.b>l2.b;
	return l1.a<l2.a;
}
double getx(line l1,line l2)//求两直线交点的x坐标 
{
	return (l2.b-l1.b)/(l1.a-l2.a);
}
void output(int top)//输出 
{
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=top;i++)
		ans[i]=s[i].dex;
	sort(ans+1,ans+1+top);
	for(int i=1;i<=top;i++)
		printf("%d ",ans[i]);
	puts("");
}
void solve()
{
	int top=0;//s的下标
	s[++top]=l[1];
	for(int i=2;i<=n;i++)//遍历直线
	{
		if(l[i].a==l[i-1].a)continue;//会被覆盖
		while(top>1&&getx(l[i],s[top])<getx(s[top],s[top-1]))top--;//可以覆盖上一条直线 
		s[++top]=l[i];
	}
	output(top);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&l[i].a,&l[i].b);
		l[i].dex=i;
	}
	sort(l+1,l+1+n,cmp);
	solve();
}