Problem p02679 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない。
    # 順にイワシを見て、直行するものをグループにする。
    # 先に単純な整数比へ変換しておく（有理数としての扱い）
    # aは整数、bは非負整数となるように整理する
    d = Counter()
    # (a, b) == (0, 0)については、他のイワシと同時に選ぶことができない。
    # 個別にカウントする。
    kodokunaiwashi = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if a == 0 and b == 0:
            kodokunaiwashi += 1
        elif b == 0:
            d[1, 0] += 1
        elif b > 0:
            g = math.gcd(b, a)
            aa = a//g
            bb = b//g
            d[aa, bb] += 1
        else:
            g = math.gcd(-b, -a)
            aa = -a//g
            bb = -b//g
            d[(aa, bb)] += 1

    # 直交するグループを考える。
    ans = 1
    for a, b in d:
        # (a, b)と直交するのは、(-b, a)と(b, -a)である。
        # このうち、有理数としてカウントしている方を採用する
        x, y = -b, a
        if y < 0:
            x = -x
            y = -y
        elif y == 0:
            x = abs(x)

        # すでに直交するイワシとしてカウントをしたらNoneとしている。
        if d[a, b] == None:
            continue

        if d[x, y] == 0:
            # 直交するイワシが存在しない場合、自由に選ぶことができる。
            ans *= pow(2, d[a, b], MOD)
            ans %= MOD
            continue
        else:
            # 直交するイワシが存在する場合、どちらかのグループから自由に選ぶ。
            # ただし、一つも選ばないという場合は、重複するためケア
            buf = pow(2, d[a, b], MOD)
            buf += pow(2, d[x, y], MOD)
            buf -= 1
            buf %= MOD
            # print(buf)
            ans *= buf
            ans %= MOD
            d[x, y] = None

    print((ans-1+kodokunaiwashi) % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from bisect import bisect_left
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない
    # イワシをソートする
    abtheta = sorted(zip(A, B), key=lambda x: math.atan2(x[1], x[0]))
    # 順にイワシを見てグループを探す。二分探索で探す。
    uf = UnionFind(N)

    circle2 = abtheta*2

    end, end2 = 0, None
    for i in range(N):
        # イワシiと90度、180度、270度角度が異なるものはありますか
        # しゃくとりで
        a, b = abtheta[i]

        # 90度の関係にあるもの
        while end <= N+i:
            ai, bi = circle2[end]
            if ai*a+bi*b <= 0:
                break
            end += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end % N)
            end += 1
            if end >= 2*N:
                break
            ai, bi = circle2[end]

        if end2 == None:
            end2 = end
            while True:
                ai, bi = circle2[end2]
                if ai*a + bi*b == 0:
                    end2 += 1
                else:
                    break

        # 180度のみなら別グループとして扱えば良いし、
        # 組み合わさるケースは別の点で検出できる

        # 270度の関係にあるもの
        while end2 <= N+i:
            ai, bi = circle2[end2]
            if ai*a+bi*b >= 0:
                break
            end2 += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end2 % N)
            end2 += 1
            if end2 >= 2*N:
                break
            ai, bi = circle2[end2]

        if end == i + 1:
            end += 1

    # デフォルトディクトに変換する
    d = defaultdict(list)
    for i in range(N):
        d[uf.root(i)].append(abtheta[i])

    ans = 1
    for key in d:
        # 各グループをさらに二つに分類
        maru, batu = 1, 0
        a0, b0 = d[key][0]
        for a, b in d[key][1:]:
            if a0 * a + b0*b == 0:
                batu += 1
            else:
                maru += 1
        buf = pow(2, maru, MOD)
        buf += pow(2, batu, MOD)
        buf -= 1
        buf %= MOD
        ans *= buf

    # print(d)
    print((ans-1) % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from bisect import bisect_left
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない
    # イワシをソートする
    abtheta = sorted(zip(A, B), key=lambda x: math.atan2(x[1], x[0]))
    # 順にイワシを見てグループを探す。二分探索で探す。
    uf = UnionFind(N)

    nisyuni = abtheta*2

    end = 0
    end2 = None
    for i in range(N):
        # イワシiと90度、180度、270度角度が異なるものはありますか
        # しゃくとりで
        a, b = abtheta[i]

        # 90度の関係にあるもの
        while end <= N+i:
            ai, bi = nisyuni[end]
            if ai*a+bi*b <= 0:
                break
            end += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end % N)
            end += 1
            if end >= 2*N:
                break
            ai, bi = nisyuni[end]

        if end2 == None:
            end2 = end

        # 270度の関係にあるもの
        while end2 <= N+i:
            ai, bi = nisyuni[end2]
            if ai*a+bi*b >= 0:
                break
            end2 += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end2 % N)
            end2 += 1
            if end2 >= 2*N:
                break
            ai, bi = nisyuni[end2]

        if end == start + 1:
            end += 1

    # デフォルトディクトに変換する
    d = defaultdict(list)
    for i in range(N):
        d[uf.root(i)].append(abtheta[i])

    ans = 1
    for key in d:
        # 各グループをさらに二つに分類
        maru, batu = 1, 0
        a0, b0 = d[key][0]
        for a, b in d[key][1:]:
            if a0 * a + b0*b == 0:
                batu += 1
            else:
                maru += 1
        buf = pow(2, maru, MOD)
        buf += pow(2, batu, MOD)
        buf -= 1
        buf %= MOD
        ans *= buf

    # print(d)
    print((ans-1) % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from bisect import bisect_left
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない
    # イワシをソートする
    theta = [0]*N
    for i, (a, b) in enumerate(zip(A, B)):
        if a != 0:
            theta[i] = math.degrees(math.atan2(b, a))
        elif b > 0:
            theta[i] = math.pi/2
        else:
            theta[i] = -math.pi/2
    # print(theta)

    abtheta = sorted(zip(theta, A, B))
    # print(*abtheta, sep="\n")
    # 順にイワシを見てグループを探す。二分探索で探す。
    uf = UnionFind(N)

    nisyu = [th for th, _, _ in abtheta]*2
    nisyuni = abtheta*2

    start, end = 0, 0
    end2 = None
    for i in range(N):
        # イワシiと90度、180度、270度角度が異なるものはありますか
        # しゃくとりで
        th, a, b = abtheta[i]

        # print("A")
        # 90度の関係にあるもの
        while end <= N+i:
            thi, ai, bi = nisyuni[end]
            if ai*a+bi*b <= 0:
                break
            end += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end % N)
            end += 1
            thi, ai, bi = nisyuni[end]

        if end2 == None:
            end2 = end

        # print("B")
        # 270度の関係にあるもの
        while end2 <= N+i:
            thi, ai, bi = nisyuni[end2]
            if ai*a+bi*b >= 0:
                break
            end2 += 1

        # print("C")
        while ai*a+bi*b == 0:
            uf.unite(i, end2 % N)
            end2 += 1
            thi, ai, bi = nisyuni[end2]

        if end == start + 1:
            end += 1

    # UFにグループ情報が格納されたので計算していく
    # print(uf.tree)

    # for i in range(N):
    #     _, ai, bi = abtheta[i]
    #     for j in range(i+1, N):
    #         _, aj, bj = abtheta[j]
    #         if ai*aj+bi*bj == 0:
    #             print("あるやん")
    #             print((ai, bi), (aj, bj))

    # return
    # デフォルトディクトに変換する
    d = defaultdict(list)
    for i in range(N):
        d[uf.root(i)].append(abtheta[i])

    ans = 1
    for key in d:
        # 各グループをさらに二つに分類
        maru = 1
        batu = 0
        th0, a0, b0 = d[key][0]
        for th, a, b in d[key][1:]:
            if a0 * a + b0*b == 0:
                batu += 1
            else:
                maru += 1
        buf = pow(2, maru, MOD)
        buf += pow(2, batu, MOD)
        buf -= 1
        buf %= MOD
        ans *= buf

    # print(d)
    print(ans-1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()