공원 산책로

Forest Frontiers 테마파크는 최근 미국 연방긴급사태관리청(FEMA)의 점검을 받았다. 가장 심각한 문제는 산책로 배치였다. 공원 관리 측이 이 문제를 해결하도록 도와 달라.

공원 지도는 좌표평면으로 나타낼 수 있다. 각 산책로는 좌표축 중 하나에 평행한 선분이다. 두 산책로는 한 점도 공유하지 않는다. 다만 선분의 끝점은 겹칠 수 있다. 대피 지점은 공원 어딘가에 있다. 이 지점은 모든 산책로 위에 있지 않거나, 산책로의 끝점과 일치한다.

비상시에는 경보가 울리고, 방문객은 대피 지점으로 가라는 안내를 받는다. FEMA 규정에 따르면 모든 방문객은 산책로를 따라서만 대피 지점에 도달할 수 있어야 하고, 이동하는 동안 대피 지점까지의 거리가 단조롭게 줄어들어야 한다. 방문객은 산책로를 벗어나지 않으므로, 경보가 울린 순간 방문객은 어느 산책로의 임의의 점에 있을 수 있다.

공원을 설계할 때는 아무도 이 규정을 고려하지 않았다. 지상 부분은 이미 완공되어 지상에 새 산책로를 지을 수 없다. 대신 지하 터널에는 산책로를 지을 수 있다. FEMA는 지하 산책로를 일반 산책로와 같게 취급한다. 대피 지점까지의 거리를 계산할 때 깊이 차이는 고려하지 않는다.

터널은 지하 산책로의 집합이다. 터널에는 다음 FEMA 규정이 추가로 적용된다.

1. 터널은 갈라질 수 없다. 입구는 정확히 두 개이고, 두 입구 사이는 하나의 직선 경로로 이어진다.
2. 각 터널 입구는 지상 산책로 위나 대피 지점에 있어야 한다.

터널은 서로 다른 깊이에 지을 수 있으므로 평면 지도에서는 교차할 수 있다. 건설비는 공원 지도 위의 길이로 계산하며 깊이는 반영하지 않는다. FEMA 규정을 지키면서 터널 전체 길이의 합이 최소가 되도록 터널을 짓는 방법을 찾아라.

첫 줄에는 산책로의 수 $N$ ($1 \le N \le 100000$)이 주어진다. 둘째 줄에는 대피 지점의 좌표 $x_e$와 $y_e$가 주어진다. 이어지는 $N$개의 줄에는 산책로 양 끝의 좌표를 나타내는 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. $x_1 = x_2$이고 $y_1 \neq y_2$이거나, $y_1 = y_2$이고 $x_1 \neq x_2$임이 보장된다. 모든 좌표는 정수이며 절댓값은 $10^8$을 넘지 않는다.

첫 줄에는 건설할 터널의 개수 $K$와 터널의 총 길이 $A$를 두 정수로 출력한다. 이어서 각 터널을 한 줄에 하나씩, 축에 평행한 선분으로 이루어진 꺾은선으로 설명한다. 한 터널의 설명은 꼭짓점의 개수(2 이상)로 시작하고, 이어서 꼭짓점의 $x$, $y$ 좌표를 한쪽 끝에서 다른 쪽 끝까지 순서대로 적는다. 모든 수는 정수이다. 인접한 두 꼭짓점은 한 좌표가 같고 다른 좌표가 달라야 한다. 모든 터널의 꼭짓점 총개수는 $10^6$을 넘을 수 없다. 출력 제한을 만족하는 최적해가 존재함이 보장된다. 여러 해가 가능하면 아무거나 출력한다. 공원이 이미 FEMA 규정을 만족하면 $K = A = 0$을 출력한다.