{"problem":{"name":"Teleportation","description":{"content":"The Republic of AtCoder lies on a Cartesian coordinate plane.   It has $N$ towns, numbered $1,2,\\dots,N$. Town $i$ is at $(x_i, y_i)$, and no two different towns are at the same coordinates. There 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":"abc226_d"},"statements":[{"statement_type":"Markdown","content":"The Republic of AtCoder lies on a Cartesian coordinate plane.  \nIt has $N$ towns, numbered $1,2,\\dots,N$. Town $i$ is at $(x_i, y_i)$, and no two different towns are at the same coordinates.\nThere are teleportation spells in the nation. A spell is identified by a pair of integers $(a,b)$, and casting a spell $(a, b)$ at coordinates $(x, y)$ teleports you to $(x+a, y+b)$.\nSnuke is a great magician who can learn the spell $(a, b)$ for any pair of integers $(a, b)$ of his choice. The number of spells he can learn is also unlimited.  \nTo be able to travel between the towns using spells, he has decided to learn some number of spells so that it is possible to do the following for every pair of different towns $(i, j)$.\n\n*   Choose **just one spell** among the spells learned. Then, repeatedly use **just** the chosen spell to get from Town $i$ to Town $j$.\n\nAt least how many spells does Snuke need to learn to achieve the objective above?\n\n## Constraints\n\n*   $2 \\leq N \\leq 500$\n*   $0 \\leq x_i \\leq 10^9$ $(1 \\leq i \\leq N)$\n*   $0 \\leq y_i \\leq 10^9$ $(1 \\leq i \\leq N)$\n*   $(x_i, y_i) \\neq (x_j, y_j)$ if $i \\neq j$.\n\n## Input\n\nInput is given from Standard Input 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":"abc226_d","tags":[],"sample_group":[["3\n1 2\n3 6\n7 4","6\n\nThe figure below illustrates the positions of the towns (along with the coordinates of the four corners).\n![image](https://img.atcoder.jp/ghi/b46a8c9c960614f791e09e6f2b7b14f9.png)\nIf Snuke learns the six spells below, he can get from Town $i$ to Town $j$ by using one of the spells once for every pair $(i,j)$ $(i \\neq j)$, achieving his objective.\n\n*   $(2, 4)$\n*   $(-2, -4)$\n*   $(4, -2)$\n*   $(-4, 2)$\n*   $(-6, -2)$\n*   $(6, 2)$\n\nAnother option is to learn the six spells below. In this case, he can get from Town $i$ to Town $j$ by using one of the spells twice for every pair $(i,j)$ $(i \\neq j)$, achieving his objective.\n\n*   $(1, 2)$\n*   $(-1, -2)$\n*   $(2, -1)$\n*   $(-2, 1)$\n*   $(-3, -1)$\n*   $(3, 1)$\n\nThere is no combination of spells that consists of less than six spells and achieve the objective, so we should print $6$."],["3\n1 2\n2 2\n4 2","2\n\nThe optimal choice is to learn the two spells below:\n\n*   $(1, 0)$\n*   $(-1, 0)$"],["4\n0 0\n0 1000000000\n1000000000 0\n1000000000 1000000000","8"]],"created_at":"2026-03-03 11:01:14"}}