[COCI 2013/2014 #3] ODAŠILJAČI

一个二维平面中有一条长度为 $d$ ，以原点为最左端，且与 $x$ 轴重合的线段 $L$。另有 $n$ 条垂直于 $x$ 轴，垂足在线段 $L$ 上，且在 $x$ 轴上方的线段 $l_1,l_2,\cdots,l_n$，其中第 $i$ 条线段到原点的距离为 $x_i$，其长度为 $h_i$。 除了线段 $L$ 之外，若干条线段的最上端装有一个大小可忽略的发光点，可以向其左右发射激光。激光只能够沿着一条直线传播，且不能够穿过任意一条线段（包括线段 $L$）。我们称线段 $L$ 中的一个点 $A$ 是被覆盖的，当且仅当存在某个发光点，使得其向某个方向发射激光，最终会落在点 $A$ 上。 现在请求出线段 $L$ 上所有被覆盖的部分的总长度。 请前往样例及样例解释以更好地理解题面。 ## Input 第一行输入两个整数 $n,d$，分别表示**除线段 $L$ 外**的线段的条数和线段 $L$ 的长度。 随后 $n$ 行，每行输入三个整数 $op_i,x_i,h_i$，分别表示第 $i$ 条线段最上端是否有发光点，第 $i$ 条线段到原点的距离和其长度。具体地，如果 $op_i=0$，则表示第 $i$ 条线段最上端没有发光点，否则表示第 $i$ 条线段最上端有发光点。 ## Output 输出一个**实数**，表示线段 $L$ 上所有被覆盖的部分的总长度。你需要保证你输出的答案和标准答案的相对误差不超过 $10^{-3}$。 [samples] ## Note **【样例 2 解释】** 下图为对应样例 2 的图片，其中加粗部分为**未被覆盖的区域**。  **【数据范围与限制】** **本题开启捆绑测试**。各个子任务的分值和特殊限制如下所述： - Subtask 1（48 pts）：$n\leqslant 10^3$。 - Subtask 2（112 pts）：无特殊限制。 对于所有数据，$1\leqslant n\leqslant 3\times 10^5$，$1\leqslant d\leqslant 10^9$，$op_i\in\{0,1\}$，$0\leqslant x_i\leqslant d$，$1\leqslant h_i\leqslant 10^9$。保证 $\forall i\neq j$，$x_i\neq x_j$。保证 $x_i$ 单调递增。 **【题目来源】** 本题来源自 **_[COCI 2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST 3](https://hsin.hr/coci/archive/2013_2014/contest3_tasks.pdf) T6 ODAŠILJAČI_**，按照原题数据配置，满分 $160$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。