自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 22:01:52，当前版本为作者最后更新于2018-05-24 16:43:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

其实这道题long double完全就可以避免扫描线时被卡精度的……

但是这道题还是避免不了被卡精度的事实，但是问题不是出在扫描线上而是出在后边的实数计算上……

还是非常考验人类智慧的精度误差问题，让我们来看一看如何和标程错的一样吧~

---

本题题解

我们可以这样想，将这个激光发射车从负无穷远处开向正无穷远处，然后取某一个时刻照射长度的最大值就是答案了

那么我们唯一要做的就是快速模拟这个过程，注意到线段是不交的，这里有一个小套路就是对于一堆互不相交的几何图形，我们随便的取一条扫描线切过去，会截出一堆点来，这些点的坐标可能会改变，但是因为图形之间没有交点，因此相对次序永远保持不变，因此我们可以使用扫描线+set的方式去维护一系列不交的几何图形(同理互不相交的圆也可以使用这个技巧去维护)

那么对于这道题我们会碰见一个非常令人难受的问题，我们要斜着做扫描线！

前置芝士：坐标系平移/旋转

坐标系平移应该大家都会吧……

假如说希望使$(x_0,y_0)$成为新坐标系的原点的话，我们可以让旧坐标系中的所有向量减去一个向量$(x_0,y_0)$就可以完成变换了

那么关键是坐标系旋转

事实上原来的标准坐标系下的一个向量$(x_{0},y_{0})$可以重新写成这样的形式

(我不是很会在luogu上打矩阵，所以请各位julao见谅)

$(x_{0},y_{0})$乘上一个单位矩阵

那么单位矩阵可以看成$(1,0),(0,1)$这两个基向量竖着摆了两列的结果

那么我们现在坐标系旋转等价于向量换基……

因此假如我们现在想让向量$(x_{1},y_{1})$成为新坐标系的x轴的话，我们可以寻找一个和这个向量垂直的向量，(显然是$(-y_{1},x_{1})$了)然后把这两个向量竖直拼起来成为一个新的矩阵

然后直接给所有需要变换的向量全部右乘上这个矩阵就可以完成换基操作了

问题来了我们会发现新的坐标系的单位长度是基向量的模长，因此我们需要给变换之后的坐标全部除一个原来向量的模长完成变换，这样我们就给所有向量重新换了一组模长为1的基了

---

那么我们现在可以把坐标系的端点平移到给出直线向量的一个端点上，现在这个直线向量的端点就是原点了，然后我们把所有点的基换成这个直线向量和与这个直线向量垂直的另一组向量就可以完成坐标系变换了,当然不要忘记除模长

(想看公式的话直接看代码好了)

那么经过了坐标系平移之后现在我们的目标直线就变成了x轴了~

有一个非常naive的想法，每个线段对着x轴做一个投影，当两个投影重叠的时候离x轴更近的投影会覆盖另一个投影，那么最后x轴会被切割成一堆权值不同的线段，然后我们可以在这一堆线段中取一个连续的区间获得相应的权值，这个问题就可以使用一些有趣的算法来解决它

但是问题来了直接暴力的复杂度不对是$O(n^2)$的

所以我们通过扫描线来快速模拟这个过程

那么我们可以将线段拆成两个事件，扫描线扫到左端点时插入这个线段，扫描线扫到右端点的时候删除这个线段

那么我们发现相邻两个事件点之间的被激光照到的线段应该是同一个线段，当然线段和x轴夹角的sec值应该是一样的

所以我们可以认为这一段投影的权值就是x轴上离x轴最近的两个线段的sec值之和

所以我们可以打一个表，$val_{i}$表示i这个事件发生之后到下一个事件发生之前中间的线段的单位长度的权值

问题来了怎么求呢？

求离x轴最近的线段……前驱后继？

我们把在x轴之上的线段插入/删除到一个set或者priority_queue里，下面的线段同理插入/删除到另一个数据结构里，然后我们在做完事件i之后查一发两个数据结构的最小最大值提取它们的sec值就可以了(如果你使用了priority_queue可能需要惰性删除)

或者你也可以只开一个set，每次upper_bound后继之后- -迭代器找前驱

那么我们现在$O(nlogn)$的求出了val数组相当于我们有了一堆不同权值的线段，现在要取一个区间使得这个区间内的线段权值之和最大

那么我们可以证明这个区间至少有一个端点必然和我们的事件点重合，否则我们总是可以向更优的一端滑动这个区间使得答案至少变得不劣

这里有一个非常自然的想法，枚举右端点紧贴的事件点，双指针求出左端点所在的线段的编号，然后使用前缀和/后缀和求出中间整块线段的权值，最后加上一个零散线段的权值即可，同理我们的左端点也需要倒着枚举一遍

于是你信心满满的写了这个算法，交上去一看，精度爆炸一分不得

你眉头一皱发现事情并不简单，因为我们处理了前缀和，这会导致精度光速下降，因此我们不能维护前缀和……

所以我们需要换一种写法，我们维护一个当前真实区间的左右端点坐标，然后维护一个离左端点最近的线段编号，维护一个离右端点最近的线段编号

然后我们每次循环的时候看一下是让左端点贴到离他最近的线段更近还是让右端点贴到离他最近的线段更近，然后选择更近的端点让它贴过去，我们发现此时你的线段是扔了一个线段的一部分加入了另一个线段的一部分，这两部分的权值都是不变的，那么长度为L的区间的权值变化量就是(加入的线段权值-丢掉的线段权值)×(挪动长度)，我们只需要把这个变化量加上原来的答案就可以了

这样的话我们只需要使用加法和乘法运算，精(he)度(std)误(cuo)差(de)较(yi)小(yang)，就可以通过本题了

可能维护双指针的算法描述的不是非常清楚，可以自己画一个图感受一下，使用文字描述并不是非常直观，或者也可以直接看代码加深理解

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;const int N=1e5+10;typedef long double ld;
int n;ld x[N][2];ld y[N][2];ld lx1;ld ly1;ld lx2;ld ly2;ld L;ld nx;int T;
ld csc[N];ld val[2*N];ld pos[2*N];int op[2*N];ld dx;ld dy;ld ans;
inline bool cmp(int a,int b){return ((a>0)?x[a][0]:x[-a][1])<((b>0)?x[b][0]:x[-b][1]);} 
struct lin//重载了operator<，每次直接暴力计算y值进行比较 
{
    int u;
    friend bool operator <(lin a,lin b)
    {
        if(a.u==b.u)return false;
        ld nya=(y[a.u][0]-y[a.u][1])/(x[a.u][0]-x[a.u][1])*(nx-x[a.u][0])+y[a.u][0];
        ld nyb=(y[b.u][0]-y[b.u][1])/(x[b.u][0]-x[b.u][1])*(nx-x[b.u][0])+y[b.u][0];
        return ((nya>0)?nya:-nya)<((nyb>0)?nyb:-nyb);
    }
};set <lin> su;set <lin> sd;//这里手懒了直接写的平衡树 
inline void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%Lf%Lf%Lf%Lf",&x[i][0],&y[i][0],&x[i][1],&y[i][1]);
    scanf("%Lf%Lf%Lf%Lf%Lf",&lx1,&ly1,&lx2,&ly2,&L);dx=lx1-lx2;dy=ly1-ly2;
    for(int i=1;i<=n;i++)//数学不好其实是正割但是这里写的是csc 
        csc[i]=sqrt((x[i][0]-x[i][1])*(x[i][0]-x[i][1])+(y[i][0]-y[i][1])*(y[i][0]-y[i][1]));
    ld dw=(lx1!=lx2)?ly1-(dy/dx)*lx1:0;ld dis=sqrt(dx*dx+dy*dy);//比较naive的坐标系变换方式，直接平移了截距 
    for(int i=1;i<=n;i++){y[i][0]-=dw;y[i][1]-=dw;}dx/=dis;dy/=dis; 
    for(int i=1;i<=n;i++)//然后直接换基就行了 
    {
        ld tr1;ld tr2;ld tr3;ld tr4;
        tr1=dx*x[i][0]+dy*y[i][0],tr2=dx*x[i][1]+dy*y[i][1],
        tr3=dx*y[i][0]-dy*x[i][0],tr4=dx*y[i][1]-dy*x[i][1];
        x[i][0]=tr1;x[i][1]=tr2;y[i][0]=tr3;y[i][1]=tr4;
    }
    for(int i=1;i<=n;i++)
        if(x[i][0]>x[i][1]){swap(x[i][0],x[i][1]);swap(y[i][0],y[i][1]);}
    for(int i=1;i<=n;i++)csc[i]/=(x[i][1]-x[i][0]);
    for(int i=1;i<=n;i++)op[i]=-i;for(int i=n+1;i<=2*n;i++)op[i]=i-n;sort(op+1,op+2*n+1,cmp);
    for(int i=1,u;i<=2*n;i++)//扫一遍扫描线 
    {
        if(op[i]>0)//插入 
        {
            u=op[i];nx=pos[i]=x[u][0];((y[u][0]>0)?su:sd).insert((lin){u});
            if(!su.empty())val[i]+=csc[su.begin()->u];
            if(!sd.empty())val[i]+=csc[sd.begin()->u];
        }else //删除 
        {
            u=-op[i];nx=pos[i]=x[u][1];((y[u][0]>0)?su:sd).erase((lin){u});
            if(!su.empty())val[i]+=csc[su.begin()->u];
            if(!sd.empty())val[i]+=csc[sd.begin()->u];
        }
    }//为了代码好写变换了下val数组，变化之后的val是上一个事件发生到这个事件发生前所夹线段的权值 
	for(int i=2*n;i>=1;i--)val[i]=val[i-1];ld ret=0;ld rl=pos[1]-L;ld rr=pos[1];int pl=1;int pr=2;
    while(pr<=2*n) 
    {
        ld dl=pos[pl]-rl;ld dr=pos[pr]-rr;//看一下是向什么方向移动更近 
        if(dl>dr){ret+=(val[pr]-val[pl])*dr;pr++;rl+=dr;rr+=dr;}
        else if (dr>dl){ret+=(val[pr]-val[pl])*dl;pl++;rl+=dl;rr+=dl;}
        else {ret+=(val[pr]-val[pl])*dl;pr++;pl++;rl+=dl;rr+=dl;}
        ans=max(ans,ret);
    }printf("%.15Lf\n",ans); 
}
inline void clear(){for(int i=1;i<=2*n;i++)val[i]=0;ans=0;}
int main(){scanf("%d",&T);for(int z=1;z<=T;z++){solve();clear();}return 0;}//拜拜程序~