题解：P16092 [ICPC 2024 NAC] Shadow Line

· · 题解

题意简述

点光源从原点沿负半轴移动，若干竖直线段在右侧墙上投下阴影。求阴影并集恰好为一个区间时，光源位置集合的总长度；若包含无界区间，输出 -1。

解题思路

设光源位于 (-t,0)，其中 t\ge 0。端点 (x_i,y_i) 投影到墙上的高度为 y_i(w+t)/(x_i+t)。

所有端点都乘上同一个正因子 w+t，它不会改变端点顺序，也不会改变区间的相交关系。因此可以忽略墙的位置，仅维护归一化后的端点高度：

f_i(t)=\frac{y_i}{x_i+t}

每个线段的下端点记为 +1，上端点记为 -1。将全部端点按当前高度升序排列，扫描它们并累加符号，得到每两个相邻端点之间的覆盖次数。

在没有端点重合的时刻，覆盖次数每回到 0，就结束一个阴影连通块。因此，所有端点后的覆盖前缀中，等于 0 的个数恰好就是连通块数，包含最后一个必为 0 的前缀。维护这个数量是否等于 1，即可判断阴影是否连通。

先判断答案是否无界。当 t 足够大时，端点顺序与原来的 y_i 顺序相同。题目保证所有纵坐标互不相同，所以这个顺序最终会稳定，不存在趋于相等却一直分离的端点。按 y_i 排序并扫描符号，若最终仅有一个连通块，之后所有足够远的光源位置都合法，直接输出 -1。

否则，最后一个端点换序事件之后不会再出现合法位置，仅需处理有限个事件之间的区间。

固定将端点按 y_i 从小到大编号。对于 i<j，有 y_i<y_j。解 f_i(t)=f_j(t)，得到唯一可能的相交时刻：

t_{i,j}=\frac{y_ix_j-y_jx_i}{y_j-y_i}

分母恒正，仅保留分子为正的事件。任意一对端点至多交换一次顺序，所以全部事件不超过 \binom{2n}{2} 个。相邻事件之间，端点顺序保持不变，连通块数也保持不变，可以一次性加上整个时间区间的长度。

事件时刻不能用浮点数排序或分组。保存分子和分母，通过交叉相乘比较；两个分数交叉乘积相等时，必须作为同一批处理。坐标限制下，分子绝对值不超过 2\times 10^{12}，分母不超过 2\times 10^6，比较乘积不超过 4\times 10^{18}，可以使用 long long 精确计算。

初始化时按 y_i/x_i 排列端点。若两个端点在 t=0 重合，则按 y_i 升序排列：这对端点的唯一相交时刻已经是 0，在所有 t>0 时都按最终的 y_i 顺序排列。这样得到的是 0 右侧的正确顺序，不需要再处理零时刻事件。

同时发生的事件不能逐条随意交换。若多个端点在同一位置相交，处理其中一对后，另一对未必仍然相邻；同一时刻也可能有多组端点分别在不同高度相交。

对同一个时刻的全部相交端点建立临时并查集，将每条事件连接的两个端点合并。一个连通分量中的端点在这个时刻具有相同高度；不同分量则对应不同的相交位置。

每个分量在事件前的端点序列中必然连续。若两个即将相交的端点之间夹着另一个端点，令时间趋近事件时刻，根据高度的连续性，中间端点也必须趋近同一个高度，因此也属于这一分量。所有这类端点对的相交事件都会被枚举到，不会漏掉中间端点。

每个分量内部的顺序在事件后完全反转。对于任意两个端点，等高条件的分子是关于 t 的一次式，且它们的纵坐标不同，所以相交前后严格交换大小关系。分量内每一对端点都换序，整体结果正好是反转，而非重新排序整个端点序列。

并查集维护每个分量在当前排列中的最小、最大位置。合并完整批次后，对每个分量对应的连续区间执行反转。设该区间为 [l,r]，其中端点符号总和不变，所以位置 r 及之后的覆盖前缀不会发生总体偏移。仅从位置 l 开始，利用未改变的前缀 s_{l-1}，重新计算到 r，并同步增减等于 0 的前缀数量即可。

不同分量的区间互不相交，可以依次处理，即使它们紧邻也不受影响。代码中的 a 保存端点排列，pos 保存每个端点在排列中的位置，sum 保存覆盖前缀，cnt 保存连通块数。并查集的 mn 和 mx 在整批事件完成合并前保持为旧排列中的区间边界。

若上一事件时刻为 a/b，当前事件时刻为 c/d，且期间 cnt==1，将这段长度加入答案。为避免接近的两个大浮点数直接相减，先精确计算差的分子，再转换为浮点数：

\frac{c}{d}-\frac{a}{b}=\frac{cb-ad}{bd}

处理有限个事件点本身不会改变总长度：即使阴影仅在某个瞬间连通，这个单点的长度也为 0。因此每次先累计前一个开放时间区间，再更新为当前事件右侧的端点顺序，已经覆盖所有需要计入的位置。

大小为 k 的相交分量包含 \binom{k}{2} 条事件，而反转及前缀重算仅需 O(k)。将所有批次合计，这部分开销不超过事件总数的常数倍。总时间复杂度由事件排序主导，为 O(n^2\log n)，空间复杂度为 O(n^2)。代码读入后将 n 加倍，后续它表示端点总数。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using ld=long double;
const int N=6005;
const int M=17997005;
struct P
{
    int x,y,op;
    bool operator<(const P &v)const{return y<v.y;}
}p[N];
struct E
{
    ll a;
    int b,u;
    bool operator<(const E &v)const{return a*v.b<v.a*b;}
}e[M];
int a[N],pos[N],sum[N],fa[N],mn[N],mx[N],vis[N],q[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
void merge(int u,int v)
{
    u=find(u);v=find(v);
    if(u==v)return;
    fa[u]=v;
    mn[v]=min(mn[v],mn[u]);
    mx[v]=max(mx[v],mx[u]);
}
void init(int u,int tag,int &cnt)
{
    if(vis[u]==tag)return;
    vis[u]=tag;
    fa[u]=u;
    mn[u]=mx[u]=pos[u];
    q[cnt++]=u;
}
bool cmp(int u,int v)
{
    ll x=1LL*p[u].y*p[v].x,y=1LL*p[v].y*p[u].x;
    return x!=y?x<y:u<v;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,w;
    cin>>n>>w;
    for(int i=0;i<n;i++)
    {
        int x,l,r;
        cin>>x>>l>>r;
        p[i*2]={x,l,1};
        p[i*2+1]={x,r,-1};
    }
    n*=2;
    sort(p,p+n);
    int cur=0,cnt=0;
    for(int i=0;i<n;i++)
    {
        cur+=p[i].op;
        cnt+=cur==0;
    }
    if(cnt==1){cout<<-1<<'\n';return 0;}
    for(int i=1;i<=n;i++)a[i]=i-1;
    sort(a+1,a+n+1,cmp);
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        pos[a[i]]=i;
        sum[i]=sum[i-1]+p[a[i]].op;
        cnt+=sum[i]==0;
    }
    int tot=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            ll num=1LL*p[i].y*p[j].x-1LL*p[j].y*p[i].x;
            if(num>0)e[tot++]={num,p[j].y-p[i].y,i*n+j};
        }
    }
    sort(e,e+tot);
    ld ans=0;
    ll pre=0;
    int den=1;
    for(int i=0;i<tot;)
    {
        int j=i+1;
        while(j<tot&&e[j].a*e[i].b==e[i].a*e[j].b)j++;
        if(cnt==1)ans+=(ld)(e[i].a*den-pre*e[i].b)/den/e[i].b;
        pre=e[i].a;
        den=e[i].b;
        int num=0;
        for(int k=i;k<j;k++)
        {
            int u=e[k].u/n,v=e[k].u%n;
            init(u,i+1,num);init(v,i+1,num);
            merge(u,v);
        }
        for(int k=0;k<num;k++)
        {
            int u=q[k];
            if(fa[u]!=u)continue;
            int l=mn[u],r=mx[u];
            reverse(a+l,a+r+1);
            for(int i=l;i<=r;i++)
            {
                cnt-=sum[i]==0;
                sum[i]=sum[i-1]+p[a[i]].op;
                cnt+=sum[i]==0;
                pos[a[i]]=i;
            }
        }
        i=j;
    }
    cout<<fixed<<setprecision(12)<<ans<<'\n';
    return 0;
}