시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 75 | 15 | 10 | 28.571% |
오랜 시간동안 바이토피아 섬은 바이짜르 왕이 다스리고 있었다. 하지만, 바이짜르 왕의 갑작스럽게 운명을 달리하자, 두 왕자 비테온과 바이테온은 어떻게 섬의 땅을 나누어 가져야 하는지로 싸우게 되었다. 결국 그들은 땅을 두 개로 나누어 점령하기로 하였다.
바이토피아 왕국은 N개의 꼭짓점이 있는 다각형의 모양이다. 다각형의 모든 변은 지도의 한 변에 평행하며, 모든 붙어있는 두 변은 서로 수직하다. 다각형의 붙어있지 않은 두 변은 내부에서 절대 만나거나 다른 변을 건드리지 않는다.
비테온과 바이테온 왕자는 이 다각형 모양의 땅을 지도의 한 변에 평행한 하나의 경계선을 이용하여 두 개의 합동인 다각형으로 나누려 한다. (두 다각형이 돌리거나 뒤집어서 같은 모양이 되면 합동이라 한다) 경계선의 양끝의 좌표는 정수여야 한다.
이런 경계선이 존재하는지를 확인하고, 존재한다면 경계선을 하나 찾아내시오.
입력의 첫 줄에는 다각형 모양의 섬을 이루는 꼭짓점의 개수 N이 주어진다. 그 뒤의 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"를 출력한다. 따옴표는 출력하지 않는다.
번호 | 배점 | 제한 |
---|---|---|
1 | 12 | 4 ≤ N ≤ 100 000. 어떠한 수직선 혹은 수평선으로 다각형을 잘랐을 때, 다각형은 정확히 두 조각으로 분할된다. |
2 | 15 | 4 ≤ N ≤ 200. |
3 | 23 | 4 ≤ N ≤ 2 000. |
4 | 50 | 4 ≤ N ≤ 100 000. |
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
6 0 0 1 0 1 1 2 1 2 2 0 2
NO
Olympiad > Baltic Olympiad in Informatics > BOI 2014 4번