Parametric Circulation

题意翻译

有一个 $n$ 个点， $m$ 条边的流网络，每条边有 $a,b,c,d$ 四个参数。 对于第 $i$ 条边，它的流量下界为 $a_it+b_i$，它的流量上界为 $c_it+d_i$。 若 $t$ 等概率为 $[0,1]$ 中的实数，求出原网络存在循环流（无源汇上下界可行流）的概率。

题目描述

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 $ $ </p><p>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.</p><p>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 $ .</p><p>Vova can't stop thinking about applications of a new topic. Right now he thinks about the following <span class="tex-font-style-it">natural</span> question: let the graph be fixed, and each value $ l\_e $ and $ r\_e $ be a linear function of a real variable $ t $ :</p><p> $ $ l_e(t) = a_e t + b_e $ $ $ $ r_e(t) = c_e t + d_e $ $ </p><p>Note that $ t $ is the <span class="tex-font-style-bf">same</span> for all edges.</p><p>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?

输入输出格式

输入格式

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 $ .

输出格式

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} $ .

输入输出样例

输入样例 #1

3 3
1 2 0 3 -4 7
2 3 -2 5 1 6
3 1 0 4 0 4

输出样例 #1

0.25

说明

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 $ $

题意翻译

有一个 $n$ 个点， $m$ 条边的流网络，每条边有 $a,b,c,d$ 四个参数。 对于第 $i$ 条边，它的流量下界为 $a_it+b_i$，它的流量上界为 $c_it+d_i$。 若 $t$ 等概率为 $[0,1]$ 中的实数，求出原网络存在循环流（无源汇上下界可行流）的概率。