{"problem":{"name":"Two Convex Sets","description":{"content":"A set of points $U$ in the $xy$\\-plane is called **good** if no point in $U$ lies in the **interior** of the convex hull of $U$. Note that the empty set is considered good. You are given $N$ distinct ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_1_h"},"statements":[{"statement_type":"Markdown","content":"A set of points $U$ in the $xy$\\-plane is called **good** if no point in $U$ lies in the **interior** of the convex hull of $U$. Note that the empty set is considered good.\nYou are given $N$ distinct points $v_1, v_2, \\dots, v_N$ in the $xy$\\-plane. The coordinates of the point $v_i$ are $(x_i, y_i)$. No three distinct points are collinear.\nCount the number of subsets $S$ of $V = \\lbrace v_1, v_2, \\dots, v_N \\rbrace$ such that both $S$ and $V \\setminus S$ are good sets.\n\n## Constraints\n\n*   All input values are integers.\n*   $1 \\le N \\le 40$\n*   $|x_i|,|y_i|\\le 10^6$\n*   $(x_i,y_i)\\neq (x_j,y_j)\\ (i\\neq j)$\n*   No three distinct points are collinear.\n\n## Input\n\nThe input is given in the following format:\n\n$N$\n$x_1$ $y_1$\n$x_2$ $y_2$\n$\\vdots$\n$x_N$ $y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_1_h","tags":[],"sample_group":[["4\n0 0\n3 0\n0 3\n1 1","14\n\nExcept for $\\emptyset$ and $V$, all other sets $S$ satisfy the condition."],["8\n1 0\n2 0\n3 1\n3 2\n2 3\n1 3\n0 2\n0 1","256"],["10\n0 0\n1 1\n7 1\n1 7\n3 2\n2 3\n4 2\n2 4\n5 4\n4 5","0"]],"created_at":"2026-03-03 11:01:14"}}