CF925F.Parametric Circulation

Vova has recently learned what a circulaton in a graph is. Recall the definition: let $G = (V, E)$ be a directed graph. A circulation $f$ is such a collection of non-negative real numbers $f_e$ ($e \in E$), that for each vertex $v \in V$ the following conservation condition holds:

$$\\sum\\limits\_{e \\in \\delta^{-}(v)} f\_e = \\sum\\limits\_{e \\in \\delta^{+}(v)} f\_e$$

where $\delta^{+}(v)$ is the set of edges that end in the vertex $v$, and $\delta^{-}(v)$ is the set of edges that start in the vertex $v$. In other words, for each vertex the total incoming flow should be equal to the total outcoming flow.

Let a $lr$-circulation be such a circulation $f$ that for each edge the condition $l_e \leq f_e \leq r_e$ holds, where $l_e$ and $r_e$ for each edge $e \in E$ are two non-negative real numbers denoting the lower and upper bounds on the value of the circulation on this edge $e$.

Vova can't stop thinking about applications of a new topic. Right now he thinks about the following natural question: let the graph be fixed, and each value $l_e$ and $r_e$ be a linear function of a real variable $t$:

l\_e(t) = a\_e t + b\_e$$ $$r\_e(t) = c\_e t + d\_e

Note that $t$ is the same for all edges.

Let $t$ be chosen at random from uniform distribution on a segment $[0, 1]$. What is the probability of existence of $lr$-circulation in the graph?

沃瓦最近学习了图中“循环流”（circulation）的概念。回顾其定义：设 $G = (V, E)$ 是一个有向图。一个循环流 $f$ 是一组非负实数 $f_e$（其中 $e \in E$），满足对每个顶点 $v \in V$，如下守恒条件成立：

$$\sum\limits_{e \in \delta^{-}(v)} f_e = \sum\limits_{e \in \delta^{+}(v)} f_e$$

其中 $\delta^{+}(v)$ 表示以顶点 $v$ 为终点的边集，$\delta^{-}(v)$ 表示以顶点 $v$ 为起点的边集。换言之，对每个顶点，总流入量应等于总流出量。

称一个循环流 $f$ 为 $lr$-循环流，若对每条边 $e$ 均满足约束 $l_e \leq f_e \leq r_e$，其中对每条边 $e \in E$，$l_e$ 和 $r_e$ 是两个非负实数，分别表示该边上循环流取值的下界与上界。

沃瓦无法停止思考这一新概念的应用。此刻他正考虑如下自然问题：图 $G$ 固定不变，且对每条边 $e$，其上下界 $l_e$ 和 $r_e$ 均为实变量 $t$ 的线性函数：

l_e(t) = a_e t + b_e$$ $$r_e(t) = c_e t + d_e

注意：所有边共享同一个变量 $t$。

设 $t$ 在区间 $[0, 1]$ 上服从均匀分布，随机选取。问：图中存在 $lr$-循环流的概率是多少？

The first line contains two integers $n$, $m$ ($1 \leq n \leq 1000$, $1 \leq m \leq 2000$).

Each of the next $m$ lines describes edges of the graph in the format $u_e$, $v_e$, $a_e$, $b_e$, $c_e$, $d_e$ ($1 \leq u_e, v_e \leq n$, $-10^4 \leq a_e, c_e \leq 10^4$, $0 \leq b_e, d_e \leq 10^4$), where $u_e$ and $v_e$ are the startpoint and the endpoint of the edge $e$, and the remaining 4 integers describe the linear functions for the upper and lower bound of circulation.

It is guaranteed that for any $t \in [0, 1]$ and for any edge $e \in E$ the following condition holds $0 \leq l_e(t) \leq r_e(t) \leq 10^4$.

第一行包含两个整数 $n$、$m$（$1 \leq n \leq 1000$，$1 \leq m \leq 2000$）。

接下来的 $m$ 行每行描述图中的一条边，格式为 $u_e$、$v_e$、$a_e$、$b_e$、$c_e$、$d_e$（其中 $1 \leq u_e, v_e \leq n$，$-10^4 \leq a_e, c_e \leq 10^4$，$0 \leq b_e, d_e \leq 10^4$），$u_e$ 和 $v_e$ 分别为边 $e$ 的起点和终点，其余四个整数用于描述该边上流的上界与下界所对应的线性函数。

保证对任意 $t \in [0, 1]$ 及任意边 $e \in E$，均有 $0 \leq l_e(t) \leq r_e(t) \leq 10^4$。

Print a single real integer — the probability of existence of $lr$-circulation in the graph, given that $t$ is chosen uniformly at random from the segment $[0, 1]$. Your answer is considered correct if its absolute difference from jury's answer is not greater than $10^{-6}$.

输出一个实数——在 $t$ 于区间 $[0, 1]$ 上均匀随机选取的前提下，图中存在 $lr$-环流的概率。若你的答案与标准答案的绝对误差不超过 $10^{-6}$，则视为正确。

In the first example the conservation condition allows only circulations with equal values $f_e$ for all three edges. The value of circulation on the last edge should be $4$ whatever $t$ is chosen, so the probability is

P(4 \\in \[3, -4t + 7\]~~\\&~~4 \\in \[-2t + 5, t + 6\]) = 0.25

在第一个例子中，守恒条件仅允许三条边上的环流值 $f_e$ 均相等。无论选择何种 $t$，最后一条边上的环流值都必须为 $4$，因此所求概率为

$$P(4 \in [3, -4t + 7]~~\&~~4 \in [-2t + 5, t + 6]) = 0.25$$