P3081 [USACO13MAR] Hill Walk G 题解

hzoi_Shadow · 2025-01-06 19:45:56 · 题解

题目传送门

前置知识

李超线段树 | 扫描线

解法

自边缘处起跳等价于找到与 x=x_{2} 相交的直线中最大的 y \le y_{2}。普通的李超线段树不支持删除操作，直接套用貌似很难处理。

观察到若能从 (x_{1},y_{1}) \to (x_{2},y_{2}) 跳跃至 (x_{1}',y_{1}') \to (x_{2}',y_{2}')，则一定有 x_{1}' \le x_{2}<x_{2}'。以 x_{1} 排序后顺次扫描线加入即可。

需要离散化和动态开点，注意计算函数值的时候要拿原值来算。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const double eps=1e-9,inf=1e18;
struct node
{
    int x1,y1,x2,y2,l,r,pos;
    bool operator < (const node &another) const
    {
        return x1<another.x1;
    }
}a[100010];
struct line
{   
    double k,b;
}li[100010];
int b[300010];
double f(int id,double x)
{
    return (id==0)?-inf:li[id].k*x+li[id].b;
}
bool cmp(int a,int b,int x)
{
    if(f(a,x)-f(b,x)>eps)  return true;
    if(f(b,x)-f(a,x)>eps)  return false;
    return a<b;
}
int sx_max(int a,int b,int x)
{
    return cmp(a,b,x)==true?a:b;
}
struct LiChao_Tree
{
    struct SegmentTree
    {
        int id;
    }tree[1200010];
    #define lson(rt) (rt<<1)
    #define rson(rt) (rt<<1|1)
    void add(int rt,int l,int r,int id)
    {
        int mid=(l+r)/2;
        if(cmp(tree[rt].id,id,b[mid])==false)
        {
            swap(tree[rt].id,id);
        }
        if(l==r)
        {
            return;
        }
        if(cmp(tree[rt].id,id,b[l])==false)
        {
            add(lson(rt),l,mid,id);
        }
        if(cmp(tree[rt].id,id,b[r])==false)
        {
            add(rson(rt),mid+1,r,id);
        }
    }
    void update(int rt,int l,int r,int x,int y,int id)
    {
        if(x<=l&&r<=y)
        {
            add(rt,l,r,id);
            return;
        }
        int mid=(l+r)/2;
        if(x<=mid)
        {
            update(lson(rt),l,mid,x,y,id);
        }
        if(y>mid)
        {
            update(rson(rt),mid+1,r,x,y,id);
        }
    }
    int query(int rt,int l,int r,int pos)
    {
        if(l==r)
        {
            return tree[rt].id;
        }
        int mid=(l+r)/2;
        if(pos<=mid)
        {
            return sx_max(tree[rt].id,query(lson(rt),l,mid,pos),b[pos]);
        }
        else
        {
            return sx_max(tree[rt].id,query(rson(rt),mid+1,r,pos),b[pos]);
        }
    }
}T;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int n,ans=0,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
        b[++b[0]]=a[i].l=a[i].x1;
        b[++b[0]]=a[i].r=a[i].x2-1;
        b[++b[0]]=a[i].pos=a[i].x2;
    }
    sort(b+1,b+1+b[0]);
    b[0]=unique(b+1,b+1+b[0])-(b+1);
    for(i=1;i<=n;i++)
    {
        a[i].l=lower_bound(b+1,b+1+b[0],a[i].l)-b;
        a[i].r=lower_bound(b+1,b+1+b[0],a[i].r)-b;
        a[i].pos=lower_bound(b+1,b+1+b[0],a[i].pos)-b;
    }
    sort(a+2,a+1+n);
    for(i=1;i<=n;i++)
    {
        li[i].k=1.0*(a[i].y2-a[i].y1)/(a[i].x2-a[i].x1);
        li[i].b=a[i].y1-li[i].k*a[i].x1;
    }   
    for(i=1,j=2;i!=0;i=T.query(1,1,b[0],a[i].pos))
    {
        ans++;
        for(;j<=n&&a[j].x1<=a[i].x2;j++)
        {
            if(a[j].x2>a[i].x2&&f(j,a[i].x2)<=a[i].y2)
            {
                T.update(1,1,b[0],a[j].l,a[j].r,j);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}