{"problem":{"name":"Ex - Intersection 2","description":{"content":"There are $N$ lines in a two-dimensional plane. The $i$\\-th line is $A_i x + B_i y + C_i = 0$. It is guaranteed that no two of the lines are parallel. In this plane, there are $\\frac{N(N-1)}{2}$ inter","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":7000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc263_h"},"statements":[{"statement_type":"Markdown","content":"There are $N$ lines in a two-dimensional plane. The $i$\\-th line is $A_i x + B_i y + C_i = 0$. It is guaranteed that no two of the lines are parallel.\nIn this plane, there are $\\frac{N(N-1)}{2}$ intersection points of two lines, including duplicates. Print the distance between the origin and the $K$\\-th nearest point to the origin among these $\\frac{N(N-1)}{2}$ points.\n\n## Constraints\n\n*   $2 \\le N \\le 5 \\times 10^4$\n*   $1 \\le K \\le \\frac{N(N-1)}{2}$\n*   $-1000 \\le |A_i|,|B_i|,|C_i| \\le 1000(1 \\le i \\le N)$\n*   No two of the lines are parallel.\n*   $A_i \\neq 0$ or $B_i \\neq 0(1 \\le i \\le N)$.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_N$ $B_N$ $C_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc263_h","tags":[],"sample_group":[["3 2\n1 1 1\n2 1 -3\n1 -1 2","2.3570226040\n\nLet us call the $i$\\-th line Line $i$.\n\n*   The intersection point of Line $1$ and Line $2$ is $(4,-5)$, whose distance to the origin is $\\sqrt{41} \\simeq 6.4031242374$.\n*   The intersection point of Line $1$ and Line $3$ is $(\\frac{-3}{2},\\frac{1}{2})$, whose distance to the origin is $\\frac{\\sqrt{10}}{2} \\simeq 1.5811388300$.\n*   The intersection point of Line $2$ and Line $3$ is $(\\frac{1}{3},\\frac{7}{3})$, whose distance to the origin is $\\frac{5\\sqrt{2}}{3} \\simeq 2.3570226040$.\n\nTherefore, the second nearest intersection point is $(\\frac{1}{3},\\frac{7}{3})$, and $\\frac{5\\sqrt{2}}{3}$ should be printed."],["6 7\n5 1 9\n4 4 -3\n8 -1 2\n0 1 -8\n4 0 -4\n2 -3 0","4.0126752298"]],"created_at":"2026-03-03 11:01:14"}}