====== Duality ======

===== 풀이 =====
  * 모든 선분이 겹치지 않게 만드는 가장 단순한 방법은, 모든 선분의 기울기를 동일하게 주는 것에서 출발하는 것이다. 이렇게 되면 모든 선분이 평행하므로 한점에서 교차할 일은 없고, 이제 겹치는 경우만 제거해주면 된다. 
  * 선분 안에 다른 점이 포함되지 않게 하기 위한 간단한 방법은, 선분이 정수 좌표를 지나가지 않도록 하는 것이다. (x2-x1) 과 (y2-y1)이 서로소가 되게 만들어주기만 하면, 선분의 양 끝점을 제외하고는 정수 좌표를 지나지 않는다. 시작점은 당연히 다른점과 겹치지 않으므로, 끝점만 다른 점과 겹치지 않게 해주면 된다.
  * 다른점과 겹치지 않게 끝점을 잡는 것은 간단하다. 시작점이 위치할수 있는 좌표 범위보다, 끝점이 위치할 수있는 좌표 범위가 10배 넓다. 그래서 시작점들의 x좌표가 [l, r] 사이에 포함되어있다면, 끝점들의 x좌표를 전부 r보다 크게 잡아주면, 끝점과 시작점이 겹칠수 없다. 
  * 이제 다 끝났다. 시작점들의 x좌표의 범위 r-l = d라고 하면, 모든 (x1,y1)을 (x1+d+1, y1+1)과 연결해주면 된다. 모든 선분의 기울기는 1/(d+1)로 동일하고, y증가량이 1이므로 x증가량과 y증가량은 서로소이며, 모든 끝점은 시작점과 겹치지 않는다. 그러므로 모든 선분은 겹치지 않는다.
  * 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 32525. Duality".

- Problem link: https://www.acmicpc.net/problem/32525
- Solution link: http://www.teferi.net/ps/problems/boj/32525

Tags: [geometry] [ad hoc]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        points = [
            [int(x) for x in sys.stdin.readline().split()] for _ in range(N)
        ]
        min_x, max_x = min(points)[0], max(points)[0]
        delta = max_x - min_x + 1

        for no, (x, y) in enumerate(points, start=1):
            print(no, x + delta, y + 1)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3 ps:teflib:linear_homogeneous_recurrence}}