F. Parametric Circulation
binary search; flows
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?
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}\).
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\)$$$