[BZOJ4049] [Cerc2014] Mountainous landscape(선분 트리 + 돌출 포켓 + 2점)

제목: 접선도를 정하고 x축이 점차적으로 증가하는 순서에 따라 제시한다.모든 라인에 대해 그 다음에 가장 작은 라인을 표시합니다.이 아래 표를 출력합니다.그중 n≤100000n≤100000.우선 우리는 이 노드가 표시하는 구간의 점의 돌출 패키지를 라인 트리로 유지해야 한다.조회할 때 우리는 현재 구간의 볼록가방이 원직선과 교차점이 있는지 판단할 수 있다. 만약에 있으면 왼쪽 나무로 돌아가고, 만약에 왼쪽 나무의 볼록가방이 원직선과 교차점이 존재한다면 직접 돌아갈 수 있으며, 그렇지 않으면 다시 오른쪽 나무로 돌아간다.하나의 볼록한 가방과 한 직선이 교차점이 있는지 신속하게 판단하려면 우리는 이분을 고려하고 벡터 포크의 기하학적 의미를 이용하면 된다.구체적으로 코드를 봅시다.만약에 댓글에 틀리면 소리 질러!코드:

#include
#include
using namespace std;
typedef long long ll;
int n;
struct Vector{
    int x,y;
    Vector(int a=0,int b=0):x(a),y(b){}
    friend ll operator*(Vector a,Vector b){
        return 1ll*a.x*b.y-1ll*b.x*a.y;
    }
    friend Vector operator-(Vector a,Vector b){
        return Vector(a.x-b.x,a.y-b.y);
    }
}a[100010];
struct Convex_hull{
    vectorc;
    void insert(Vector a){
        for(int j=c.size();j>1&&(a-c[j-2])*(c[j-1]-c[j-2])<=0;j--)
            c.pop_back();
        c.push_back(a);
        return;
    }
    bool check(Vector a,Vector b){
        int l=0,r=c.size()-2;
        while(lint mid=(l+r)>>1;
            if((c[mid]-a)*(b-a)1]-a)*(b-a))
                r=mid;
            else l=mid+1;
        }
        return (c[l]-a)*(b-a)<0||(c[l+1]-a)*(b-a)<0;
    }
}tr[400010];
void build(int o,int l,int r){
    if(l==r){
        tr[o].insert(a[l]);
        tr[o].insert(a[l+1]);
        return;
    }
    for(int i=l;i<=r+1;i++)
        tr[o].insert(a[i]);
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    return;
}
int query(int o,int l,int r,int L,int R,Vector a,Vector b){
    if(L<=l&&r<=R){
        if(!tr[o].check(a,b))
            return 0;
        if(l==r)
            return l;
    }
    int mid=(l+r)>>1,ret=0;
    if(L<=mid)
        ret=query(o<<1,l,mid,L,R,a,b);
    if(!ret&&R>mid)
        ret=query(o<<1|1,mid+1,r,L,R,a,b);
    return ret;
}
int rd(){
    int x=0;
    char c;
    do c=getchar();
    while(!isdigit(c));
    do{
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }while(isdigit(c));
    return x;
}
int main(){
    n=rd();
    for(int i=1;i<=n;i++)
        a[i].x=rd(),a[i].y=rd();
    build(1,1,n-1);
    for(int i=1;i<=n-1;i++)
        printf("%d ",query(1,1,n-1,i+1,n-1,a[i],a[i+1]));
    return 0;
}