看似一个半平面交

但是一般的半平面交用求的是凸包，这个是一个凸壳。封闭区间和半开放区间还是有区别的。

当然一般的半平面交其实可以，只要把向量的方向设对即可（只有1/4象限的向量）

 

但是既然直接给了斜率的话，而且半开放的区间，还有一个简单一些的做法：

考虑直线按照斜率排序，斜率相同纵截距排序

两个栈，一个维护交点，一个维护直线

加入一个直线，如果和最后一个直线的交点在前一个交点的左方（或者重合），那么这个直线和交点都被盖住了。

不断一起弹栈

画个图就很好理解。

O(nlogn+n)

#include
      
       #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.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
        
         n) break;        while(top1&&calc(l[i],zhan[top2])
        
       
      

 

一个不错的应用题是：

转化之后就是横着的“水平可见直线”