{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Geometríalandia es una extraña ciudad en un plano infinito donde hay $n$ calles infinitas representadas por rectas. Cada una de ellas es descrita por una ecuación $a_ix + b_iy + c_i \u003d 0$, donde no puede ocurrir que $a_i$ y $b_i$ sean cero a la vez.\n\nEstas calles dividen a Geometríalandia en regiones, algunas posiblemente de tamaño infinito. Diremos que estas regiones son las cuadras de la ciudad.\n\nGeometrita es una estudiante de la FCGM (Facultad de Ciencias Geométricas Matemáticas). Su casa y la FCGM están ubicadas en cuadras de la ciudad.\n\nDiremos que dos cuadras son adyacentes si comparten un borde de largo mayor a cero. En un paso, Geometrita se puede mover de una cuadra a otra adyacente.\n\nGeometrita debe rendir un control de Geometría I en 30 minutos, pero recién salió de su casa. Para ayudarla, determina la mínima cantidad de pasos que debe realizar desde la cuadra de su casa hasta la cuadra de la FCGM.\n"}},{"title":"Entrada","value":{"format":"MD","content":"La primera línea contiene dos enteros $x_1, y_1$ separados por espacios ($-10^6 \\leq x_1, y_1 \\leq 10^6$), indicando las coordenadas de la casa de Geometrita.\n\nLa segunda línea contiene dos enteros $x_2, y_2$ separados por espacios ($-10^6 \\leq x_2, y_2 \\leq 10^6$), indicando las coordenadas de la FCGM.\n\nLa tercera línea contiene un entero $n$ ($1 \\leq n \\leq 300$), indicando la cantidad de calles en Geometríalandia.\n\nLas siguientes $n$ líneas contiene tres enteros separados por espacios $a_i, b_i, c_i$ ($-10^6 \\leq a_i, b_i, c_i \\leq 10^6, |a_i|+|b_i|\u003e0$), los coeficientes de la calle $a_ix + b_iy + c_i \u003d 0$.\n\nSe garantiza que no hay dos calles iguales. Además, ni la casa de Geometrita ni la FCGM están en una calle."}},{"title":"Salida","value":{"format":"MD","content":"Imprime la menor cantidad de pasos para llegar desde la casa de Geometrita hasta la FCGM."}},{"title":"Ejemplo 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSalida\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1\n-1 -1\n2\n0 1 0\n1 0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Ejemplo 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSalida\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1\n-1 -1\n3\n1 0 0\n0 1 0\n1 1 -3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Nota","value":{"format":"MD","content":"\n\nA continuación se muestran imágenes de los ejemplos. (El punto A representa la casa y B la universidad, y diferentes cuadras tienen diferentes colores).\n\u003ccenter\u003e\n \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/944e2cf33bb301e3a81336be85e7bd6d?v\u003d1684781488\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\n\u003c/center\u003e\n\u003ccenter\u003e\n \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/67aebcebefeaebb1574a19580337fc18?v\u003d1684781488\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\n\u003c/center\u003e"}}]}