看似一个半平面交
但是一般的半平面交用求的是凸包，这个是一个凸壳。封闭区间和半开放区间还是有区别的。
当然一般的半平面交其实可以，只要把向量的方向设对即可（只有1/4象限的向量）
但是既然直接给了斜率的话，而且半开放的区间，还有一个简单一些的做法：
考虑直线按照斜率排序，斜率相同纵截距排序
两个栈，一个维护交点，一个维护直线
加入一个直线，如果和最后一个直线的交点在前一个交点的左方（或者重合），那么这个直线和交点都被盖住了。
不断一起弹栈
画个图就很好理解。
O(nlogn+n)
#include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^‘0‘) using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch==‘-‘)&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=50000+5; struct po{ double x,y; bool friend operator <(po a,po b){ if(a.x!=b.x) return a.x<b.x; return a.y>=b.y; } }sta[N]; int top1; int n; struct line{ int k,b; int id; bool friend operator <(line a,line b){ if(a.k==b.k) return a.b>b.b; return a.k<b.k; } }l[N],zhan[N]; int top2; int ans[N],tot; po calc(line a,line b){//warning!!! pingxing !! po ret; ret.x=((double)b.b-(double)a.b)/((double)a.k-(double)b.k); ret.y=b.k*ret.x+b.b; return ret; } int main(){ rd(n); for(reg i=1;i<=n;++i){ rd(l[i].k);rd(l[i].b); l[i].id=i; } sort(l+1,l+n+1); zhan[++top2]=l[1]; for(reg i=2;i<=n;++i){ while(i<=n&&l[i].k==l[i-1].k) ++i; if(i>n) break; while(top1&&calc(l[i],zhan[top2])<sta[top1]){ --top1;--top2; } sta[++top1]=calc(l[i],zhan[top2]); zhan[++top2]=l[i]; } for(reg i=1;i<=top2;++i){ ans[++tot]=zhan[i].id; } sort(ans+1,ans+tot+1); for(reg i=1;i<=tot;++i){ printf("%d ",ans[i]); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/26 15:19:22 */
一个不错的应用题是：
转化之后就是横着的“水平可见直线”
原文：https://www.cnblogs.com/Miracevin/p/10182519.html
