题目描述

一个二维平面中有一条长度为 $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$ 上所有被覆盖的部分的总长度。

请前往样例及样例解释以更好地理解题面。

输入格式

第一行输入两个整数 $n,d$，分别表示除线段 $L$ 外的线段的条数和线段 $L$ 的长度。

随后 $n$ 行，每行输入三个整数 $op_i,x_i,h_i$，分别表示第 $i$ 条线段最上端是否有发光点，第 $i$ 条线段到原点的距离和其长度。具体地，如果 $op_i=0$，则表示第 $i$ 条线段最上端没有发光点，否则表示第 $i$ 条线段最上端有发光点。

输出格式

输出一个实数，表示线段 $L$ 上所有被覆盖的部分的总长度。你需要保证你输出的答案和标准答案的相对误差不超过 $10^{-3}$。

3 10
1 2 6
0 4 3
0 8 2

6.000000

5 15
0 4 3
1 5 5
1 6 6
0 9 2
0 10 3

8.500000

提示

【样例 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$。

【题目来源】

本题来源自 COCI 2013-2014 CONTEST 3 T6 ODAŠILJAČI，按照原题数据配置，满分 $160$ 分。

由 Eason_AC 翻译整理提供。