시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2 2 2 100.000%

문제

오랜 시간동안 바이토피아 섬은 바이짜르 왕이 다스리고 있었다. 하지만, 바이짜르 왕의 갑작스럽게 운명을 달리하자, 두 왕자 비테온과 바이테온은 어떻게 섬의 땅을 나누어 가져야 하는지로 싸우게 되었다. 결국 그들은 땅을 두 개로 나누어 점령하기로 하였다.

바이토피아 왕국은 N개의 꼭짓점이 있는 다각형의 모양이다. 다각형의 모든 변은 지도의 한 변에 평행하며,  모든 붙어있는 두 변은 서로 수직하다. 다각형의 붙어있지 않은 두 변은 내부에서 절대 만나거나 다른 변을 건드리지 않는다.

비테온과 바이테온 왕자는 이 다각형 모양의 땅을 지도의 한 변에 평행한 하나의 경계선을 이용하여 두 개의 합동인 다각형으로 나누려 한다. (두 다각형이 돌리거나 뒤집어서 같은 모양이 되면 합동이라 한다) 경계선의 양끝의 좌표는 정수여야 한다.

이런 경계선이 존재하는지를 확인하고, 존재한다면 경계선을 하나 찾아내시오.

입력

입력의 첫 줄에는 다각형 모양의 섬을 이루는 꼭짓점의 갯수 N(4 ≤ N ≤ 105)이 주어진다. 그 뒤의 N개의 줄에는 정점의 좌표 Xi, Yi (0 ≤ Xi, Yi ≤ 109) 가 순서대로 주어진다.

즉, 섬은 (X1, Y1) − (X2, Y2), (X2, Y2) − (X3, Y3), ... , (XN−1, YN−1) − (XN , YN ), (XN, YN ) − (X1, Y1)의 선분들로 이루어져 있는 것이다. 위에도 언급되어 있지만 붙어있는 두 선분은 언제나 서로 수직하다.

출력

섬을 합동인 두 다각형으로 나누는 선분이 존재하면, 선분의 두 끝점이 (x1, y1), (x2, y2)일 때 x1, y1, x2, y2를 나타내는 4개의 정수를 한 줄에 출력하면 된다. x1=x2이거나 y1=y2여야 한다. 선분은 다각형의 안쪽에 있어야 하며, 선분의 양 끝점은 다각형의 경계선에 있어야 한다. 그런 선분이 여러개이면 그 중에 하나를 출력한다.

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

예제 입력

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

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2014 4번

  • 문제를 번역한 사람: junis3