{"problem":{"name":"F. Parametric Circulation","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF925F"},"statements":[{"statement_type":"Markdown","content":"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:\n\n\\\\sum\\\\limits_{e \\\\in \\\\delta^{-}(v)} f_e = \\\\sum\\\\limits_{e \\\\in \\\\delta^{+}(v)} f_e\n\nwhere $\\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.\n\nLet 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$.\n\nVova 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$:\n\nl_e(t) = a_e t + b_e r_e(t) = c_e t + d_e\n\nNote that $t$ is the **same** for all edges.\n\nLet $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?\n\n## Input\n\nThe first line contains two integers $n$, $m$ ($1 \\leq n \\leq 1000$, $1 \\leq m \\leq 2000$).\n\nEach 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.\n\nIt 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\n## Output\n\nPrint 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}$.\n\n[samples]\n\n## Note\n\nIn 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\n\nP(4 \\\\in \\[3, -4t + 7\\]~~\\\\&~~4 \\\\in \\[-2t + 5, t + 6\\]) = 0.25","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vova 最近学习了图中的 _循环_（circulation）概念。回顾定义：设 $G = (V, E)$ 为一个有向图。一个循环 $f$ 是一组非负实数 $f_e$（$e \\in E$），满足对每个顶点 $v \\in V$ 都有以下 _守恒_ 条件：\n\n$$\\sum\\limits_{e \\in \\delta^{-}(v)} f_e = \\sum\\limits_{e \\in \\delta^{+}(v)} f_e$$\n\n其中 $\\delta^{+}(v)$ 是所有以 $v$ 为终点的边的集合，$\\delta^{-}(v)$ 是所有以 $v$ 为起点的边的集合。换句话说，对每个顶点，总流入流量应等于总流出流量。\n\n设一个 $l$-$r$-循环 是指一个循环 $f$，满足对每条边 $e \\in E$ 都有条件 $l_e \\leq f_e \\leq r_e$，其中 $l_e$ 和 $r_e$ 是每条边 $e$ 的非负实数，分别表示该边上循环值的下界和上界。\n\nVova 不停地思考这一新主题的应用。现在他思考这样一个 _自然_ 的问题：设图是固定的，每条边的 $l_e$ 和 $r_e$ 都是实变量 $t$ 的线性函数：\n\n$$l_e(t) = a_e t + b_e$$ $$r_e(t) = c_e t + d_e$$\n\n注意，所有边的 $t$ 是相同的。\n\n现从区间 $[0, 1]$ 上的均匀分布中随机选取 $t$。求图中存在 $l$-$r$-循环的概率？\n\n第一行包含两个整数 $n$, $m$（$1 \\leq n \\leq 1000$, $1 \\leq m \\leq 2000$）。\n\n接下来的 $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$ 的起点和终点，其余四个整数描述该边上循环值的上下界线性函数。\n\n保证对任意 $t \\in [0, 1]$ 和任意边 $e \\in E$，都有 $0 \\leq l_e(t) \\leq r_e(t) \\leq 10^4$。\n\n输出一个实数 —— 在 $t$ 从区间 $[0, 1]$ 上均匀随机选取时，图中存在 $l$-$r$-循环的概率。你的答案与标准答案的绝对误差不超过 $10^{-6}$ 时被视为正确。\n\n在第一个例子中，守恒条件仅允许所有三条边上的循环值相等。无论 $t$ 取何值，最后一条边上的循环值必须为 $4$，因此概率为\n\n$$P(4 \\in [3, -4t + 7]~~\\&~~4 \\in [-2t + 5, t + 6]) = 0.25$$\n\n## Input\n\n第一行包含两个整数 $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$。\n\n## Output\n\n输出一个实数 —— 在 $t$ 从区间 $[0, 1]$ 上均匀随机选取时，图中存在 $l$-$r$-循环的概率。你的答案与标准答案的绝对误差不超过 $10^{-6}$ 时被视为正确。\n\n[samples]\n\n## Note\n\n在第一个例子中，守恒条件仅允许所有三条边上的循环值相等。无论 $t$ 取何值，最后一条边上的循环值必须为 $4$，因此概率为$$P(4 \\in [3, -4t + 7]~~\\&~~4 \\in [-2t + 5, t + 6]) = 0.25$$","is_translate":true,"language":"Chinese"}],"meta":{"iden":"CF925F","tags":["binary search","flows"],"sample_group":[["3 3\n1 2 0 3 -4 7\n2 3 -2 5 1 6\n3 1 0 4 0 4","0.25"]],"created_at":"2026-03-03 11:00:39"}}