题解：P3081 [USACO13MAR] Hill Walk G

Soh_paramEEMS · 2025-07-10 20:55:27 · 题解

题意

题目传送门。

思路

因为线段没有交点，所以漫步路径是唯一的。走完一座山之后，将会下到哪座山是固定的。

有线段想用李超线段树。但是走到一座山的终点的时候，无法确定具体哪一座山峰：可能头顶有一座，哪怕没有李超树也只能返回终点的 y。删线段？不会捏。

本质还是模拟漫步过程。我们记下每座山的起点终点信息，每到一座山的起点就把山加进 set 里（set 支持 O(\log n) 查询和删除）。记录当前登山编号 now，初始时 now=1。

我们每走到山 now 的终点，就要下山。走完一座山之后，将会下到哪座山是固定的，即每座山的“前继”是固定的，我们想要 set 的指针前移就能走到对应的山。

首先，若遍历到一个终点不是 now 的终点，就应该把当前点所在山删掉，以免影响下山。其次，我们想要找到一个排序规则，使 set 按照这个顺序将山峰从高到低排好序。

排序规则：比较 a,b 的上下关系，可以借助二者终点连线 c 来比较，如下图已清晰说明。

• 1. 当 $k_b<k_c$ 时，$a<b$（如 $a_1,b,c_1$）； 2. 反之 $k_c<k_b$ 时，$b<a$，$a$ 可以落到 $b$（如 $a_2,b,c_2$）。 不用 $a,c$ 比较的反例，如 $a_2'$ 所示。
• 1. 当 $k_c<k_a$ 时，$a<b$（如 $a_1,b,c_1$）； 2. 反之 $k_a<k_c$ 时，$b<a$，$b$ 可以落到 $a$（如 $a_2,b,c_2$）。 不用 $a,b$ 比较的反例，如 $b'$ 所示。

排序规则代码示例：

dd slope(dd xa,dd ya,dd xb,dd yb)
{
    return (ya-yb)/(xa-xb);
}
bool operator < (hill a,hill b)//a<b,b在a上 
{
    dd ka=slope(a.xa,a.ya,a.xb,a.yb);
    dd kb=slope(b.xa,b.ya,b.xb,b.yb);
    dd kc=slope(a.xb,a.yb,b.xb,b.yb);
    if(a.xb<b.xb)return kb<kc;
    return kc<ka;
}

在 set 上获取直接前继，可以用指针移动。

储存起点和终点，记得开 2 倍空间。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
const ll N=2e5+9;
ll n;
struct hill
{
    dd xa,ya,xb,yb;
    ll id;
}b[N];
dd slope(dd xa,dd ya,dd xb,dd yb)
{
    return (ya-yb)/(xa-xb);
}
bool operator < (hill a,hill b)//a<b,b在a上 
{
    dd ka=slope(a.xa,a.ya,a.xb,a.yb);
    dd kb=slope(b.xa,b.ya,b.xb,b.yb);
    dd kc=slope(a.xb,a.yb,b.xb,b.yb);
    if(a.xb<b.xb)return kb<kc;
    return kc<ka;
}
set<hill>S;
struct point
{
    dd x,y;
    ll id;
}P[N<<1];
bool cmp(point x,point y)
{
    if(x.x!=y.x)return x.x<y.x;
    return x.y<y.y;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        dd xa,ya,xb,yb;
        scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb);
        b[i]=(hill){xa,ya,xb,yb,i};
        P[i*2-1]=(point){xa,ya,i};
        P[i*2]=(point){xb,yb,i};
    }
    S.insert(b[1]);
    sort(P+1,P+2*n+1,cmp);
    ll ans=1,now=1;
    for(int i=2;i<=n*2;i++)
    {
        ll id=P[i].id;
        if(b[id].xa==P[i].x)//起点
        {
            S.insert(b[id]);
            continue;
        }
        if(now!=id)S.erase(b[id]);//没走到遍历的这座山
        else 
        {
            set<hill>::iterator B=S.find(b[id]);//走到终点了 
            if(B==S.begin())break;//无山可走
            B--,now=B->id;//下山 
            ans++;
        }
    }
    printf("%lld",ans);
    return 0;
}