{"problem":{"name":"三色","description":{"content":"给定 $n$ 个三元组 $(a_i,b_i,c_i)$。$q$ 次询问，每次给定一个集合 $S$，查询是否存在实数三元组 $(p,q,r)$ 满足：对于所有满足 $pa_i+qb_i+r>0$ 的 $i$，其 $c_i$ 构成的集合恰好为 $S$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9685"},"statements":[{"statement_type":"Markdown","content":"给定 $n$ 个三元组 $(a_i,b_i,c_i)$。$q$ 次询问，每次给定一个集合 $S$，查询是否存在实数三元组 $(p,q,r)$ 满足：对于所有满足 $pa_i+qb_i+r>0$ 的 $i$，其 $c_i$ 构成的集合恰好为 $S$。\n\n## Input\n\n第一行输入一个整数 $T$，代表数据组数。\n\n对于每组数据，第一行输入三个数 $n,q,k$，其中 $k=|S|$。\n\n接下来 $n$ 行，每行输入三个整数 $a_i,b_i,c_i$。\n\n接下来 $q$ 行，第 $i$ 行输入 $k$ 个整数 $s_{i,1},s_{i,2},\\dots,s_{i,k}$，代表第 $i$ 组询问中 $S$ 的元素。保证元素不重复。\n\n## Output\n\n对于每组数据，输出一行一个长为 $q$ 的字符串 $R$，对于第 $i$ 组询问，若答案为存在，则 $R_i$ 为 $\\tt 1$，否则为 $\\tt 0$。\n\n[samples]\n\n## Background\n\n我的心脏还在跳动着啊。\n\n## Note\n\n### 数据规模与约定\n\n对于所有数据，$1\\le n,\\sum n\\le 10^5$，$1\\le q,\\sum q \\le 3\\times 10^5$，$1\\le k\\le 3$，$1\\le c_i,s_{i,j}\\le n$，$|a_i|,|b_i|\\le 10^9$。\n\n对于任意 $i\\neq j$，保证 $(a_i,b_i)\\neq (a_j,b_j)$，且不存在 $(p,q)$ 和三个不同的下标 $i,j,k$ 满足 $pa_i+qb_i=pa_j+qb_j=pa_k+qb_k$。\n\n### 子任务\n\n| # | 特殊性质 | 分值 |\n| :----------: | :----------: | :----------: |\n| 0 | 样例 | 0 |\n| 1 | $n\\le 3$ | 2 |\n| 2 | $k=1$ | 11 |\n| 3 | $\\sum n^2\\le 10^6$ | 23 |\n| 4 | $k=2$ | 29 |\n| 5 | $k=3$ | 35 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9685","tags":["计算几何","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3\n5 2 1\n3 0 1\n-2 2 2\n1 -3 3\n-2 -1 4\n0 0 5\n2\n5\n5 4 2\n3 0 1\n-2 2 2\n1 -3 3\n-2 -1 4\n0 0 5\n2 3\n2 4\n5 1\n3 5\n5 6 3\n3 0 1\n-2 2 2\n1 -3 3\n-2 -1 4\n0 0 5\n3 5 4\n2 5 3\n4 2 1\n2 4 3\n3 1 2\n3 1 4","10\n0110\n100101"]],"created_at":"2026-03-03 11:09:25"}}