{"problem":{"name":"C. Line-line Intersection","description":{"content":"There are $n$ lines $l_1, l_2, \\\\dots, l_n$ on the 2D-plane. Staring at these lines, Calabash is wondering how many pairs of $(i, j)$ that $1 <= i < j <= n$ and $l_i, l_j$ share at least one common p","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10222C"},"statements":[{"statement_type":"Markdown","content":"There are $n$ lines $l_1, l_2, \\\\dots, l_n$ on the 2D-plane.\n\nStaring at these lines, Calabash is wondering how many pairs of $(i, j)$ that $1 <= i < j <= n$ and $l_i, l_j$ share at least one common point. Note that two overlapping lines also share common points.\n\nPlease write a program to solve Calabash's problem.\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.\n\nIn each test case, there is one integer $n (1 <= n <= 100000)$ in the first line, denoting the number of lines.\n\nFor the next $n$ lines, each line contains four integers $x a_i, y a_i, x b_i, y b_i (| x a_i |, | y a_i |, | x b_i |, | y b_i | <= 10^9)$. It means $l_i$ passes both $(x a_i, y a_i)$ and $(x b_i, y b_i)$. $(x a_i, y a_i)$ will never be coincided with $(x b_i, y b_i)$.\n\nIt is guaranteed that $sum n <= 10^6$.\n\nFor each test case, print a single line containing an integer, denoting the answer.\n\n## Input\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there is one integer $n (1 <= n <= 100000)$ in the first line, denoting the number of lines.For the next $n$ lines, each line contains four integers $x a_i, y a_i, x b_i, y b_i (| x a_i |, | y a_i |, | x b_i |, | y b_i | <= 10^9)$. It means $l_i$ passes both $(x a_i, y a_i)$ and $(x b_i, y b_i)$. $(x a_i, y a_i)$ will never be coincided with $(x b_i, y b_i)$.It is guaranteed that $sum n <= 10^6$.\n\n## Output\n\nFor each test case, print a single line containing an integer, denoting the answer.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k, m_k \\in \\mathbb{Z}^+ $ denote the lengths of the plaintext-ciphertext pair and the target ciphertext, respectively.  \n- Let $ P_k = p_1 p_2 \\dots p_{n_k} \\in \\{A, B, \\dots, Z\\}^{n_k} $ be the plaintext string.  \n- Let $ C_k = c_1 c_2 \\dots c_{n_k} \\in \\{A, B, \\dots, Z\\}^{n_k} $ be the corresponding ciphertext.  \n- Let $ Q_k = q_1 q_2 \\dots q_{m_k} \\in \\{A, B, \\dots, Z\\}^{m_k} $ be the target ciphertext to decrypt.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 50 $  \n2. $ 1 \\le n_k, m_k \\le 50 $  \n3. All strings consist solely of uppercase English letters.  \n4. The shift $ s_k \\in \\{0, 1, \\dots, 25\\} $ mapping $ P_k $ to $ C_k $ is unique and satisfies:  \n   $$\n   c_i \\equiv p_i + s_k \\pmod{26}, \\quad \\forall i \\in \\{1, \\dots, n_k\\}\n   $$  \n   where letters are mapped to integers $ A \\to 0, B \\to 1, \\dots, Z \\to 25 $.  \n\n**Objective**  \nFor each test case $ k $, determine the shift $ s_k $ from $ P_k $ and $ C_k $, then decrypt $ Q_k $ using the inverse shift $ -s_k \\mod 26 $ to obtain plaintext $ D_k = d_1 d_2 \\dots d_{m_k} $, where:  \n$$\nd_i \\equiv q_i - s_k \\pmod{26}\n$$  \nOutput $ D_k $ as a string.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10222C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}