{"problem":{"name":"Middle Point","description":{"content":"Initially, $N$ points $(x_1, y_1), \\ldots, (x_N, y_N)$ are plotted on a plane. Snuke is allowed to perform the following operation an arbitrary finite number of times: *   Choose two points that are ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc051_e"},"statements":[{"statement_type":"Markdown","content":"Initially, $N$ points $(x_1, y_1), \\ldots, (x_N, y_N)$ are plotted on a plane. Snuke is allowed to perform the following operation an arbitrary finite number of times:\n\n*   Choose two points that are already plotted, and plot the middle point of the two chosen points (if the middle point hasn't been plotted yet). The coordinates of the middle point don't necessarily have to be integers.\n\nAfter he finish performing operations, his score is the number of plotted points with integer coordinates (including the initial points). Compute the maximum score he can get.\n\n## Constraints\n\n*   $3 \\leq N \\leq 100$\n*   $0 \\leq x_i, y_i \\leq 10^9$\n*   No three points are on the same line.\n*   All values in the input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$:$\n$x_N$ $y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc051_e","tags":[],"sample_group":[["4\n0 0\n0 2\n2 0\n2 2","9\n\nOne possible way to achieve the maximum score is as follows:\n\n*   Initially, four points $(0, 0), (0, 2), (2, 0), (2, 2)$ are plotted.\n*   Plot $(0, 1)$: the middle point of $(0, 0)$ and $(0, 2)$.\n*   Plot $(0, 0.5)$: the middle point of $(0, 0)$ and $(0, 1)$.\n*   Plot $(1, 0)$: the middle point of $(0, 0)$ and $(2, 0)$.\n*   Plot $(1, 1)$: the middle point of $(0, 0)$ and $(2, 2)$.\n*   Plot $(1, 2)$: the middle point of $(0, 2)$ and $(2, 2)$.\n*   Plot $(2, 1)$: the middle point of $(2, 0)$ and $(2, 2)$.\n*   Now we have $10$ points: $(0, 0), (0, 0.5), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)$. $9$ of them have integer coordinates, so the score is $9$."],["4\n0 0\n0 3\n3 0\n3 3","4\n\nWe can prove that, besides the initial points, he can't plot any points with integer coordinates."]],"created_at":"2026-03-03 11:01:14"}}