놀라운 볼록 껍질

왕실 카지노에는 슬롯 머신이 많이 놓인 거대한 방이 있다. 카지노 관리자는 이 방이 길을 찾기 너무 쉬워서, 사람들이 큰 손해 없이 방을 빠져나갈 가능성이 높다고 판단했다. 이를 바로잡기 위해 관리자는 슬롯 머신의 위치와 그 사이를 잇는 직선 통로를 복잡하게 설계하여 사람들이 길을 잃기 쉽게 만들었다.

방의 모양은 대략 타원형이다. 방이 비어 있다면 방 안 어느 지점에서든 방 전체를 관찰할 수 있다. $N$대의 슬롯 머신은 각각 점으로 표현되며, 고유한 수익 값을 하나씩 가진다. 관리자는 아래 설명대로 슬롯 머신들을 통로로 연결하려 한다.

벽에는 이미 슬롯 머신이 3대 이상 설치되어 있다. 벽에 설치된 슬롯 머신은 모두 직선 통로로 연결되어, 방 전체를 둘러싸는 닫힌 외곽 경로를 이뤄야 한다. 나머지 슬롯 머신이 있다면, 모두 외곽 경로가 둘러싼 영역 안에 있다.

방은 직선 통로에 의해 여러 개의 작은 구역으로 나뉘며, 각 구역은 자기만의 외곽 경로로 둘러싸인다. 나누는 과정은 두 단계로 진행된다.

1단계. 외곽 경로 위의 슬롯 머신이 4대 이상이면, 기준이 되는 피벗 슬롯 머신 두 대를 고른다. 첫 번째 피벗은 외곽 경로 위에서 수익이 가장 큰 슬롯 머신이다. 두 번째 피벗도 외곽 경로 위에 있으며, 첫 번째 피벗에서 가장 먼 슬롯 머신이다. 거리는 외곽 경로를 따라 잰다. 한 슬롯 머신에서 다른 슬롯 머신까지 가려면 지나야 하는 통로의 개수가 거리다. 가장 먼 슬롯 머신이 두 대라면 수익이 더 큰 쪽을 두 번째 피벗으로 고른다. 두 피벗을 잇는 새 통로가 외곽 경로 안쪽을 두 영역으로 나눈다. 새로 생긴 각 영역의 외곽 경로는, 원래 외곽 경로의 일부 중 새 통로와 함께 그 작은 영역을 감싸는 닫힌 경로를 이루는 최소 부분이다. 더 이상 새 영역을 만들 수 없을 때까지 이 과정을 반복한다.

2단계. 1단계가 끝나면 2단계가 시작된다. 내부에 통로가 없는 영역 $A$에 대해, 그 안에 있는 모든 슬롯 머신을 살핀다. 슬롯 머신이 있다면, 그중 수익이 가장 큰 것을 $A$의 외곽 경로 $P_A$ 위의 모든 슬롯 머신과 통로로 잇는다. 이렇게 영역은 더 작은 영역들로 나뉜다. 새로 생긴 각 영역의 외곽 경로는 $P_A$의 통로 한 개와 새로 만든 통로 두 개로 이루어진다. 각 영역은 이 세 통로가 만드는 삼각형 안에 있으며, 그 안에 다른 통로는 없다. 더 이상 새 영역을 만들 수 없을 때까지 반복한다.

관리자는 이 설계의 수익성을 평가하려 한다. 그래서 고수익 구성을 정의한다. 고수익 구성은 모든 쌍이 통로로 직접 연결된 슬롯 머신들의 집합 가운데 크기가 최대인 집합이다. 관심 있는 수익성 지표는 세 가지다. 첫 번째는 고수익 구성 하나의 크기다. 두 번째는 설계에 존재하는 고수익 구성의 개수다. 세 번째는 적어도 하나의 고수익 구성에 속하는 슬롯 머신의 개수다.

첫 줄에 정수 $N$ ($3 \le N \le 10^5$)이 주어진다. $N$은 슬롯 머신의 개수다. 이어지는 $N$개의 줄에는 각각 정수 $X$와 $Y$ ($0 \le X, Y \le 10^9$)가 주어지며, 슬롯 머신 한 대의 위치를 나타낸다. 슬롯 머신은 수익 값이 큰 순서로 나열되어 있다. 세 슬롯 머신이 한 직선 위에 놓이는 경우는 없다.

세 가지 수익성 지표를 출력한다.