아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

양분

시간 제한1초메모리 제한256 MB

요약
축에 평행한 단순 다각형을 정수 좌표의 축평행 절단선 하나로 합동인 두 조각으로 나누고, 없으면 없다고 판정합니다.
난이도

어려움10점 중 9점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

바이토피아 섬은 오랫동안 바이짜르 왕이 다스렸다. 바이짜르 왕이 갑자기 세상을 떠나자 두 왕자 비테온과 바이테온은 섬의 땅을 어떻게 나눌지를 두고 다투었고, 결국 땅을 두 조각으로 갈라 하나씩 차지하기로 했다.

바이토피아의 땅은 꼭짓점이 NN개인 다각형이다. 모든 변은 xx축이나 yy축에 평행하고, 이웃한 두 변은 서로 수직이다. 이웃하지 않은 두 변은 서로 만나지 않으므로 이 다각형은 단순 다각형이다.

두 왕자는 축에 평행한 선분 하나로 이 땅을 합동인 두 다각형으로 나누려 한다. 두 다각형을 돌리거나 뒤집어서 완전히 포갤 수 있으면 합동이다. 선분의 두 끝점은 좌표가 모두 정수여야 한다.

이런 선분이 있는지 판정하고, 있으면 출력 규칙이 정하는 선분 하나를 찾아라.

입력

첫째 줄에 다각형의 꼭짓점 개수 NN이 주어진다 (4≤N≤10004 \le N \le 1000, NN은 짝수).

다음 NN개 줄에 꼭짓점의 좌표 XiX_i와 YiY_i가 다각형을 한 방향으로 따라가는 순서대로 주어진다 (0≤Xi,Yi≤1090 \le X_i, Y_i \le 10^9).

즉 땅의 경계는 선분 (X1,Y1)−(X2,Y2)(X_1, Y_1)-(X_2, Y_2), (X2,Y2)−(X3,Y3)(X_2, Y_2)-(X_3, Y_3), …\dots, (XN−1,YN−1)−(XN,YN)(X_{N-1}, Y_{N-1})-(X_N, Y_N), (XN,YN)−(X1,Y1)(X_N, Y_N)-(X_1, Y_1)로 이루어진다. 이웃한 두 선분은 항상 서로 수직이다.

출력

땅을 합동인 두 다각형으로 나누는 선분이 있으면, 그 선분의 두 끝점 (x1,y1)(x_1, y_1)과 (x2,y2)(x_2, y_2)를 x1x_1 y1y_1 x2x_2 y2y_2 순서로 한 줄에 출력한다. x1=x2x_1 = x_2이거나 y1=y2y_1 = y_2여야 한다. 두 끝점은 다각형의 경계 위에 있어야 하고, 두 끝점을 뺀 선분의 나머지 점은 모두 다각형의 내부에 있어야 한다.

조건을 만족하는 선분이 여러 개일 수 있다. 이때는 다음 규칙으로 하나만 고른다. 먼저 각 선분의 두 끝점을 (x1,y1)≤(x2,y2)(x_1, y_1) \le (x_2, y_2)가 되도록 놓는다. 즉 x1<x2x_1 < x_2이거나, x1=x2x_1 = x_2이고 y1≤y2y_1 \le y_2이다. 그다음 네 정수 (x1,y1,x2,y2)(x_1, y_1, x_2, y_2)를 이 순서로 비교해 사전순으로 가장 앞서는 선분을 출력한다.

그런 선분이 없으면 NO를 출력한다. 따옴표는 출력하지 않는다.

예제3

  1. 예제 1

    입력
    10
    0 0
    1 0
    1 1
    3 1
    3 5
    2 5
    2 3
    1 3
    1 2
    0 2
    
    예상 출력
    1 2 3 2
    
  2. 예제 2

    입력
    6
    0 0
    1 0
    1 1
    2 1
    2 2
    0 2
    
    예상 출력
    NO
    
  3. 예제 3

    입력
    4
    0 0
    2 0
    2 2
    0 2
    
    예상 출력
    0 1 2 1