{"problem":{"name":"Do use hexagon grid","description":{"content":"We have an infinite hexagonal grid shown below. Initially, all squares are white. ![image](https://img.atcoder.jp/abc269/b61b1e0469588c61352a7fa7f7865351.png) A hexagonal cell is represented as $(i,j)","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc269_d"},"statements":[{"statement_type":"Markdown","content":"We have an infinite hexagonal grid shown below. Initially, all squares are white.\n![image](https://img.atcoder.jp/abc269/b61b1e0469588c61352a7fa7f7865351.png)\nA hexagonal cell is represented as $(i,j)$ with two integers $i$ and $j$.  \nCell $(i,j)$ is adjacent to the following six cells:\n\n*   $(i-1,j-1)$\n*   $(i-1,j)$\n*   $(i,j-1)$\n*   $(i,j+1)$\n*   $(i+1,j)$\n*   $(i+1,j+1)$\n\nTakahashi has painted $N$ cells $(X_1,Y_1),(X_2,Y_2),\\dots,(X_N,Y_N)$ black.  \nFind the number of connected components formed by the black cells.  \nTwo black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.\n\n## Constraints\n\n*   All values in the input are integers.\n*   $1 \\le N \\le 1000$\n*   $|X_i|,|Y_i| \\le 1000$\n*   The pairs $(X_i,Y_i)$ are distinct.\n\n## Input\n\nThe input 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":"abc269_d","tags":[],"sample_group":[["6\n-1 -1\n0 1\n0 2\n1 0\n1 2\n2 0","3\n\nAfter Takahashi paints cells black, the grid looks as shown below.\n![image](https://img.atcoder.jp/abc269/865747dac44d93b150ecbed462ac4ef3.png)\nThe black squares form the following three connected components:\n\n*   $(-1,-1)$\n*   $(1,0),(2,0)$\n*   $(0,1),(0,2),(1,2)$"],["4\n5 0\n4 1\n-3 -4\n-2 -5","4"],["5\n2 1\n2 -1\n1 0\n3 1\n1 -1","1"]],"created_at":"2026-03-03 11:01:14"}}