ABC269 D — Do use hexagon grid

1# -*- coding: utf-8 -*-2 3 4class UnionFind:5    '''Represents a data structure that tracks a set of elements partitioned6       into a number of disjoint (non-overlapping) subsets.7 8    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.9 10    See:11    https://www.youtube.com/watch?v=zV3Ul2pA2Fw12    https://en.wikipedia.org/wiki/Disjoint-set_data_structure13    https://atcoder.jp/contests/abc120/submissions/444494214    '''15 16    def __init__(self, number_count: int):17        '''18        Args:19            number_count: The size of elements (greater than 2).20        '''21        self.parent_numbers = [-1 for _ in range(number_count)]22 23    def find_root(self, number: int) -> int:24        '''Follows the chain of parent pointers from number up the tree until25           it reaches a root element, whose parent is itself.26        Args:27            number: The trees id (0-index).28 29        Returns:30            The index of a root element.31        '''32        if self.parent_numbers[number] < 0:33            return number34 35        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])36        return self.parent_numbers[number]37 38    def get_group_size(self, number: int) -> int:39        '''40        Args:41            number: The trees id (0-index).42 43        Returns:44            The size of group.45        '''46        return -self.parent_numbers[self.find_root(number)]47 48    def is_same_group(self, number_x: int, number_y: int) -> bool:49        '''Represents the roots of tree number_x and number_y are in the same50           group.51        Args:52            number_x: The trees x (0-index).53            number_y: The trees y (0-index).54        '''55        return self.find_root(number_x) == self.find_root(number_y)56 57    def merge_if_needs(self, number_x: int, number_y: int) -> bool:58        '''Uses find_root to determine the roots of the tree number_x and59           number_y belong to. If the roots are distinct, the trees are combined60           by attaching the roots of one to the root of the other.61        Args:62            number_x: The trees x (0-index).63            number_y: The trees y (0-index).64        '''65        x = self.find_root(number_x)66        y = self.find_root(number_y)67 68        if x == y:69            return False70 71        if self.get_group_size(x) >= self.get_group_size(y):72            self.parent_numbers[x] += self.parent_numbers[y]73            self.parent_numbers[y] = x74        else:75            self.parent_numbers[y] += self.parent_numbers[x]76            self.parent_numbers[x] = y77        return True78 79 80def main():81    import sys82 83    input = sys.stdin.readline84 85    n = int(input())86    xy = [tuple(map(int, input().split())) for _ in range(n)]87    dxy = [(-1, -1), (-1, 0), (0, -1), (0, 1), (1, 0), (1, 1)]88    uf = UnionFind(n)89 90    for i in range(n):91        xi, yi = xy[i]92 93        for j in range(i):94            xj, yj = xy[j]95 96            dx = xi - xj97            dy = yi - yj98 99            if (dx, dy) in dxy:100                uf.merge_if_needs(i, j)101    102    ans = set()103 104    for i in range(n):105        ans.add(uf.find_root(i))106 107    print(len(ans))108 109 110if __name__ == "__main__":111    main()112