상위집합

평면 위의 점들의 집합에서 임의의 두 점에 대해 다음 세 조건 중 적어도 하나가 참이면, 이 집합을 좋은 집합이라고 한다.

• 두 점이 같은 수평선 위에 있다.
• 두 점이 같은 수직선 위에 있다.
• 두 점을 꼭짓점으로 하는 직사각형의 내부 또는 경계에 이 두 점 이외의 집합의 점이 적어도 하나 있다. 여기서 직사각형은 변이 좌표축과 평행한 두 점의 so 경계 상자를 뜻한다.

평면 위의 n개 점으로 이루어진 집합이 주어진다. 크기가 2·105개 점을 초과하지 않는, 주어진 집합의 임의의 좋은 상위집합을 구한다.

첫 번째 줄에는 초기 집합의 점 개수인 정수 n (1 ≤ n ≤ 104)이 주어진다. 다음 n개의 줄에는 집합의 점들이 주어진다. 각 줄에는 해당 점의 좌표인 두 정수 xi와 yi ( - 109 ≤ xi, yi ≤ 109)가 주어진다. 모든 점이 서로 다름이 보장된다.

첫 번째 줄에 좋은 상위집합의 점 개수 m (n ≤ m ≤ 2·105)을 출력하고, 다음 m개의 줄에 점들을 출력한다. 점의 좌표의 절댓값은 109를 초과해서는 안 된다. m을 최소화할 필요는 없으며, 크기가 2·105를 초과하지 않는 주어진 집합의 임의의 좋은 상위집합을 찾으면 충분하다는 점에 유의한다.

상위집합의 모든 점은 정수 좌표를 가져야 한다.