Off by One (Codeforces 1519E)
Tags: Others, geometry

There are $$$n$$$ points on an infinite plane. The $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$ such that $$$x_i > 0$$$ and $$$y_i > 0$$$. The coordinates are not necessarily integer.In one move you perform the following operations:   choose two points $$$a$$$ and $$$b$$$ ($$$a \neq b$$$);  move point $$$a$$$ from $$$(x_a, y_a)$$$ to either $$$(x_a + 1, y_a)$$$ or $$$(x_a, y_a + 1)$$$;  move point $$$b$$$ from $$$(x_b, y_b)$$$ to either $$$(x_b + 1, y_b)$$$ or $$$(x_b, y_b + 1)$$$;  remove points $$$a$$$ and $$$b$$$. However, the move can only be performed if there exists a line that passes through the new coordinates of $$$a$$$, new coordinates of $$$b$$$ and $$$(0, 0)$$$. Otherwise, the move can't be performed and the points stay at their original coordinates $$$(x_a, y_a)$$$ and $$$(x_b, y_b)$$$, respectively.The numeration of points does not change after some points are removed. Once the points are removed, they can't be chosen in any later moves. Note that you have to move both points during the move, you can't leave them at their original coordinates.What is the maximum number of moves you can perform? What are these moves?If there are multiple answers, you can print any of them.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points.The $$$i$$$-th of the next $$$n$$$ lines contains four integers $$$a_i, b_i, c_i, d_i$$$ ($$$1 \le a_i, b_i, c_i, d_i \le 10^9$$$). The coordinates of the $$$i$$$-th point are $$$x_i = \frac{a_i}{b_i}$$$ and $$$y_i = \frac{c_i}{d_i}$$$.

Output: In the first line print a single integer $$$c$$$ — the maximum number of moves you can perform.Each of the next $$$c$$$ lines should contain a description of a move: two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — the points that are removed during the current move. There should be a way to move points $$$a$$$ and $$$b$$$ according to the statement so that there's a line that passes through the new coordinates of $$$a$$$, the new coordinates of $$$b$$$ and $$$(0, 0)$$$. No removed point can be chosen in a later move.If there are multiple answers, you can print any of them. You can print the moves and the points in the move in the arbitrary order.

Note: Here are the points and the moves for the ones that get chosen for the moves from the first example:  

Sample Inputs:
7
4 1 5 1
1 1 1 1
3 3 3 3
1 1 4 1
6 1 1 1
5 1 4 1
6 1 1 1

4
2 1 1 1
1 1 2 1
2 1 1 2
1 2 1 2

4
182 168 60 96
78 72 45 72
69 21 144 63
148 12 105 6

Sample Outputs:
3
1 6
2 4
5 7

1
1 2

1
2 4

Solution (Python):
import io
import os
from collections import defaultdict
from math import gcd
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def solve(N, points):
    compress = defaultdict(lambda : len(compress))
    edges = []
    for (i, (a, b, c, d)) in enumerate(points):
        edge = []
        for (dx, dy) in [(0, 1), (1, 0)]:
            (x, y) = (a * d + d * b * dx, c * b + d * b * dy)
            g = gcd(x, y)
            x //= g
            y //= g
            edge.append(compress[x, y])
        edges.append(edge)
    graph = [[] for i in range(len(compress))]
    for (label, (u, v)) in enumerate(edges):
        graph[u].append((v, label))
        graph[v].append((u, label))
    depth = [-1] * len(graph)
    parent = [-1] * len(graph)
    usedPoints = [0] * N
    ans = []

    @bootstrap
    def dfs(node, p, d):
        depth[node] = d
        parent[node] = p
        for (child, label) in graph[node]:
            if depth[child] == -1:
                yield dfs(child, node, d + 1)
        descendants = []
        ancestors = []
        for (nbr, label) in graph[node]:
            if not usedPoints[label]:
                assert depth[nbr] != -1
                if depth[nbr] > d:
                    descendants.append(label)
                else:
                    assert depth[nbr] < d
                    ancestors.append(label)
        pairs = descendants + ancestors
        for i in range(1, len(pairs), 2):
            x = pairs[i - 1]
            y = pairs[i]
            usedPoints[x] = 1
            usedPoints[y] = 1
            ans.append(str(x + 1) + ' ' + str(y + 1))
        yield
    for root in range(len(graph)):
        if depth[root] == -1:
            dfs(root, -1, 0)
    return str(len(ans)) + '\n' + '\n'.join(ans)
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    TC = 1
    for tc in range(1, TC + 1):
        (N,) = [int(x) for x in input().split()]
        points = [[int(x) for x in input().split()] for i in range(N)]
        ans = solve(N, points)
        print(ans)

Solution (Python):
def divisors(M):
    d = []
    i = 1
    while M >= i ** 2:
        if M % i == 0:
            d.append(i)
            if i ** 2 != M:
                d.append(M // i)
        i = i + 1
    return d

def popcount(x):
    x = x - (x >> 1 & 1431655765)
    x = (x & 858993459) + (x >> 2 & 858993459)
    x = x + (x >> 4) & 252645135
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 127

def eratosthenes(n):
    res = [0 for i in range(n + 1)]
    prime = set([])
    for i in range(2, n + 1):
        if not res[i]:
            prime.add(i)
            for j in range(1, n // i + 1):
                res[i * j] = 1
    return prime

def factorization(n):
    res = []
    for p in prime:
        if n % p == 0:
            while n % p == 0:
                n //= p
            res.append(p)
    if n != 1:
        res.append(n)
    return res

def euler_phi(n):
    res = n
    for x in range(2, n + 1):
        if x ** 2 > n:
            break
        if n % x == 0:
            res = res // x * (x - 1)
            while n % x == 0:
                n //= x
    if n != 1:
        res = res // n * (n - 1)
    return res

def ind(b, n):
    res = 0
    while n % b == 0:
        res += 1
        n //= b
    return res

def isPrimeMR(n):
    if n == 1:
        return 0
    d = n - 1
    d = d // (d & -d)
    L = [2, 3, 5, 7, 11, 13, 17]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1:
            continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1:
                return 0
            t <<= 1
    return 1

def findFactorRho(n):
    from math import gcd
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        (y, r, q, g) = (2, 1, 1, 1)
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)

def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    (ret[n], n) = (1, 1)
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:
        ret[n] = 1
    if rhoFlg:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(n):
    res = [1]
    prime = primeFactor(n)
    for p in prime:
        newres = []
        for d in res:
            for j in range(prime[p] + 1):
                newres.append(d * p ** j)
        res = newres
    res.sort()
    return res

def xorfactorial(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    elif num == 2:
        return 3
    elif num == 3:
        return 0
    else:
        x = baseorder(num)
        return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
    if n == 0:
        res = [X[0] * Y[0] % mod]
        return res
    x = [digit[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    z = [digit[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
    res1 = xorconv(n - 1, x, y)
    res2 = xorconv(n - 1, z, w)
    former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
    latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
    former = list(map(lambda x: x % mod, former))
    latter = list(map(lambda x: x % mod, latter))
    return former + latter

def merge_sort(A, B):
    (pos_A, pos_B) = (0, 0)
    (n, m) = (len(A), len(B))
    res = []
    while pos_A < n and pos_B < m:
        (a, b) = (A[pos_A], B[pos_B])
        if a < b:
            res.append(a)
            pos_A += 1
        else:
            res.append(b)
            pos_B += 1
    res += A[pos_A:]
    res += B[pos_B:]
    return res

class UnionFindVerSize:

    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.group = N

    def find_root(self, x):
        if self._parent[x] == x:
            return x
        self._parent[x] = self.find_root(self._parent[x])
        stack = [x]
        while self._parent[stack[-1]] != stack[-1]:
            stack.append(self._parent[stack[-1]])
        for v in stack:
            self._parent[v] = stack[-1]
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy:
            return
        self.group -= 1
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.val = [0 for i in range(N)]
        self.flag = True
        self.edge = [[] for i in range(N)]

    def dfs(self, v, pv):
        stack = [(v, pv)]
        new_parent = self.parent[pv]
        while stack:
            (v, pv) = stack.pop()
            self.parent[v] = new_parent
            for (nv, w) in self.edge[v]:
                if nv != pv:
                    self.val[nv] = self.val[v] + w
                    stack.append((nv, v))

    def unite(self, x, y, w):
        if not self.flag:
            return
        if self.parent[x] == self.parent[y]:
            self.flag = self.val[x] - self.val[y] == w
            return
        if self.size[self.parent[x]] > self.size[self.parent[y]]:
            self.edge[x].append((y, -w))
            self.edge[y].append((x, w))
            self.size[x] += self.size[y]
            self.val[y] = self.val[x] - w
            self.dfs(y, x)
        else:
            self.edge[x].append((y, -w))
            self.edge[y].append((x, w))
            self.size[y] += self.size[x]
            self.val[x] = self.val[y] + w
            self.dfs(x, y)

class Dijkstra:

    class Edge:

        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        self.G = [[] for i in range(V)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        return self._E

    @property
    def V(self):
        return self._V

    def add_edge(self, _from, _to, _cost):
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        import heapq
        que = []
        d = [10 ** 15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))
        while len(que) != 0:
            (cost, v) = heapq.heappop(que)
            if d[v] < cost:
                continue
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    heapq.heappush(que, (d[e.to], e.to))
        return d

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0] * N
    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i + j < N and s[j] == s[i + j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z_alg[k] < j:
            Z_alg[i + k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

class BIT:

    def __init__(self, n, mod=0):
        self.BIT = [0] * (n + 1)
        self.num = n
        self.mod = mod

    def query(self, idx):
        res_sum = 0
        mod = self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            if mod:
                res_sum %= mod
            idx -= idx & -idx
        return res_sum

    def update(self, idx, x):
        mod = self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            if mod:
                self.BIT[idx] %= mod
            idx += idx & -idx
        return

class dancinglink:

    def __init__(self, n, debug=False):
        self.n = n
        self.debug = debug
        self._left = [i - 1 for i in range(n)]
        self._right = [i + 1 for i in range(n)]
        self.exist = [True for i in range(n)]

    def pop(self, k):
        if self.debug:
            assert self.exist[k]
        L = self._left[k]
        R = self._right[k]
        if L != -1:
            if R != self.n:
                (self._right[L], self._left[R]) = (R, L)
            else:
                self._right[L] = self.n
        elif R != self.n:
            self._left[R] = -1
        self.exist[k] = False

    def left(self, idx, k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._left[res]
            if res == -1:
                break
            k -= 1
        return res

    def right(self, idx, k=1):
        if self.debug:
            assert self.exist[idx]
        res = idx
        while k:
            res = self._right[res]
            if res == self.n:
                break
            k -= 1
        return res

class SparseTable:

    def __init__(self, A, merge_func, ide_ele):
        N = len(A)
        n = N.bit_length()
        self.table = [[ide_ele for i in range(n)] for i in range(N)]
        self.merge_func = merge_func
        for i in range(N):
            self.table[i][0] = A[i]
        for j in range(1, n):
            for i in range(0, N - 2 ** j + 1):
                f = self.table[i][j - 1]
                s = self.table[i + 2 ** (j - 1)][j - 1]
                self.table[i][j] = self.merge_func(f, s)

    def query(self, s, t):
        b = t - s + 1
        m = b.bit_length() - 1
        return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

    class node:

        def __init__(self, val):
            self.left = None
            self.right = None
            self.max = val

    def __init__(self):
        self.root = self.node(-10 ** 15)

    def append(self, key, val):
        pos = self.root
        for i in range(29, -1, -1):
            pos.max = max(pos.max, val)
            if key >> i & 1:
                if pos.right is None:
                    pos.right = self.node(val)
                    pos = pos.right
                else:
                    pos = pos.right
            elif pos.left is None:
                pos.left = self.node(val)
                pos = pos.left
            else:
                pos = pos.left
        pos.max = max(pos.max, val)

    def search(self, M, xor):
        res = -10 ** 15
        pos = self.root
        for i in range(29, -1, -1):
            if pos is None:
                break
            if M >> i & 1:
                if xor >> i & 1:
                    if pos.right:
                        res = max(res, pos.right.max)
                    pos = pos.left
                else:
                    if pos.left:
                        res = max(res, pos.left.max)
                    pos = pos.right
            elif xor >> i & 1:
                pos = pos.right
            else:
                pos = pos.left
        if pos:
            res = max(res, pos.max)
        return res

def solveequation(edge, ans, n, m):
    x = [0] * m
    used = [False] * n
    for v in range(n):
        if used[v]:
            continue
        y = dfs(v)
        if y != 0:
            return False
    return x

    def dfs(v):
        used[v] = True
        r = ans[v]
        for (to, dire, id) in edge[v]:
            if used[to]:
                continue
            y = dfs(to)
            if dire == -1:
                x[id] = y
            else:
                x[id] = -y
            r += y
        return r

class Matrix:
    mod = 10 ** 9 + 7

    def set_mod(m):
        Matrix.mod = m

    def __init__(self, L):
        self.row = len(L)
        self.column = len(L[0])
        self._matrix = L
        for i in range(self.row):
            for j in range(self.column):
                self._matridigit[i][j] %= Matrix.mod

    def __getitem__(self, item):
        if type(item) == int:
            raise IndexError('you must specific row and column')
        elif len(item) != 2:
            raise IndexError('you must specific row and column')
        (i, j) = item
        return self._matridigit[i][j]

    def __setitem__(self, item, val):
        if type(item) == int:
            raise IndexError('you must specific row and column')
        elif len(item) != 2:
            raise IndexError('you must specific row and column')
        (i, j) = item
        self._matridigit[i][j] = val

    def __add__(self, other):
        if (self.row, self.column) != (other.row, other.column):
            raise SizeError('sizes of matrixes are different')
        res = [[0 for j in range(self.column)] for i in range(self.row)]
        for i in range(self.row):
            for j in range(self.column):
                res[i][j] = self._matridigit[i][j] + other._matridigit[i][j]
                res[i][j] %= Matrix.mod
        return Matrix(res)

    def __sub__(self, other):
        if (self.row, self.column) != (other.row, other.column):
            raise SizeError('sizes of matrixes are different')
        res = [[0 for j in range(self.column)] for i in range(self.row)]
        for i in range(self.row):
            for j in range(self.column):
                res[i][j] = self._matridigit[i][j] - other._matridigit[i][j]
                res[i][j] %= Matrix.mod
        return Matrix(res)

    def __mul__(self, other):
        if type(other) != int:
            if self.column != other.row:
                raise SizeError('sizes of matrixes are different')
            res = [[0 for j in range(other.column)] for i in range(self.row)]
            for i in range(self.row):
                for j in range(other.column):
                    temp = 0
                    for k in range(self.column):
                        temp += self._matridigit[i][k] * other._matrix[k][j]
                    res[i][j] = temp % Matrix.mod
            return Matrix(res)
        else:
            n = other
            res = [[n * self._matridigit[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
            return Matrix(res)

    def __pow__(self, m):
        if self.column != self.row:
            raise MatrixPowError('the size of row must be the same as that of column')
        n = self.row
        res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
        while m:
            if m % 2 == 1:
                res = res * self
            self = self * self
            m //= 2
        return res

    def __str__(self):
        res = []
        for i in range(self.row):
            for j in range(self.column):
                res.append(str(self._matridigit[i][j]))
                res.append(' ')
            res.append('\n')
        res = res[:len(res) - 1]
        return ''.join(res)
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
n = int(input())
next = 0
node = {}
edge = [[] for i in range(2 * n)]
for i in range(n):
    (a, b, c, d) = mi()
    (q, p) = (b * c, (a + b) * d)
    g = gcd(q, p)
    (q, p) = (q // g, p // g)
    if (q, p) in node:
        u = node[q, p]
    else:
        node[q, p] = next
        next += 1
        u = node[q, p]
    (q, p) = (b * (c + d), a * d)
    g = gcd(q, p)
    (q, p) = (q // g, p // g)
    if (q, p) in node:
        v = node[q, p]
    else:
        node[q, p] = next
        next += 1
        v = node[q, p]
    edge[u].append((v, i))
    edge[v].append((u, i))
edge = edge[:next]
N = len(edge)
ans = []
visited = [False for v in range(N)]
parent = [(-1, -1) for v in range(N)]
used = [False for v in range(n)]
cnt = [0 for v in range(N)]
for start in range(N):
    if visited[start]:
        continue
    visited[start] = True
    stack = [start]
    while stack:
        v = stack[-1]
        if len(edge[v]) == cnt[v]:
            idx = []
            for (nv, i) in edge[v]:
                if nv == parent[v][0]:
                    continue
                if not used[i]:
                    used[i] = True
                    idx.append(i)
            if len(idx) & 1 and parent[v] != (-1, -1):
                used[parent[v][1]] = True
                idx.append(parent[v][1])
            for i in range(0, len(idx) - 1, 2):
                ans.append((idx[i], idx[i + 1]))
            stack.pop()
        else:
            (nv, i) = edge[v][cnt[v]]
            cnt[v] += 1
            if visited[nv]:
                continue
            visited[nv] = True
            parent[nv] = (v, i)
            stack.append(nv)
print(len(ans))
for (u, v) in ans:
    print(u + 1, v + 1)

Solution (Python):
import sys
from sys import stdin
import math
from collections import deque
n = int(stdin.readline())
dic = {}
lis = []
for i in range(n):
    (a, b, c, d) = map(int, stdin.readline().split())
    (A, B, C, D) = (a + b, b, c, d)
    siA = C * B
    boA = D * A
    g = math.gcd(siA, boA)
    siA //= g
    boA //= g
    if (siA, boA) not in dic:
        dic[siA, boA] = len(dic)
        lis.append([])
    (A, B, C, D) = (a, b, c + d, d)
    siB = C * B
    boB = D * A
    g = math.gcd(siB, boB)
    siB //= g
    boB //= g
    if (siB, boB) not in dic:
        dic[siB, boB] = len(dic)
        lis.append([])
    va = dic[siA, boA]
    vb = dic[siB, boB]
    lis[va].append((vb, i))
    lis[vb].append((va, i))
ans = []
used = [False] * (3 * n)
nexedge = [0] * (3 * n)
able = [True] * (3 * n)
pedge = [None] * (3 * n)
for v in range(len(lis)):
    if not able[v]:
        continue
    stk = [v]
    able[v] = False
    while stk:
        v = stk[-1]
        if len(lis[v]) <= nexedge[v]:
            elis = []
            for (nex, ind) in lis[v]:
                if ind != pedge[v] and (not used[ind]):
                    elis.append(ind)
            if pedge[v] != None and (not used[pedge[v]]):
                elis.append(pedge[v])
            for i in range(1, len(elis), 2):
                ans.append((elis[i - 1] + 1, elis[i] + 1))
                used[elis[i - 1]] = True
                used[elis[i]] = True
            del stk[-1]
            continue
        (nex, ind) = lis[v][nexedge[v]]
        nexedge[v] += 1
        if able[nex]:
            pedge[nex] = ind
            able[nex] = False
            stk.append(nex)
print(len(ans))
for i in ans:
    print(*i)