直线牛 题解

维护单调栈以记录可见直线。

首先需要对这些直线排序，以斜率k为第一关键字（a.k>b.k），若斜率相等（即平行），则按截距b排序（a.b>b.b）。

直接在这里说明一下：接下来将直线入栈时，判断这条直线是否与上一条平行，若平行，则continue。一定要将第0条直线的斜率赋值为正无穷，或者在判断平行时同时特判i>1。

不难发现，一条直线是否有一部分可见取决于它与其他直线的交点，那么我们写一个cross返回交点横坐标：

return (double)(a[p].b-a[q].b)/(double)(a[q].k-a[p].k);

交点式很好推：

k1*x+b1 = k2*x+b2
(k2-k1)*x = b1-b2
x = (b1-b2)/(k2-k1)

请注意求交点根本不用在意纵坐标...

下面是另一个难点：如何通过交点横坐标的大小关系判断这条栈顶直线是否会被覆盖弹出？ 请看下图：

假设绿线2为当前top，那么当红线3进栈时，左图蓝色部分仍然可见，而右图的绿线2则完全被覆盖（上半部分黄线1比他高，下半部分红线3比他高）。不难发现造成这两种情况不同的是两个灰色交点的左右位置关系

如果当前直线与栈顶直线的交点的横坐标比栈顶与栈顶上一条直线的交点更靠右，就是右图这种情况：2,3交点比1,2交点更靠右，那么栈顶这条直线就完全被覆盖不可见了。

记得保存答案后先排序再输出。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+7;
int n,top,t[N],ans[N];
struct node{
	int k,b,id;
}a[N];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
bool cmp(node p,node q){
	if(p.k==q.k)return p.b>q.b;
	return p.k>q.k;
}
double cross(int p,int q){
	return (double)(a[p].b-a[q].b)/(double)(a[q].k-a[p].k);
}
signed main(){
	//freopen("line.txt","r",stdin);
	n=read();
	for(int i = 1;i<=n;i++){
		a[i].k=read();a[i].b=read();
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	a[0].k=0x7f7f7f7f;
	for(int i = 1;i<=n;i++){
		if(a[i].k==a[i-1].k)continue;//平行
		while(top>1&&(cross(t[top],i)>=cross(t[top],t[top-1])))top--;
		t[++top]=i;
		ans[top]=a[i].id;
	}
	sort(ans+1,ans+1+top);
	for(int i = 1;i<=top;i++)write(ans[i]),putchar(' ');
	return 0;
}