단순 사각형

평면상에서 어떤 로봇이 수평 또는 수직으로 선을 그으면서 움직인다. 이 로봇은 처음 정해진 위치에서 시작하여 움직인 뒤 다시 처음 위치로 되돌아 온다.

로봇이 움직이는 방향은 위(UP), 아래(DOWN), 오른쪽(RIGHT), 왼쪽(LEFT) 4가지 뿐이며, 이는 각각 \(U\), \(D\), \(R\), \(L\)로 표시된다. 또 움직인 거리는 양의 정수이다. 움직임은 방향과 거리로써 표현되는데 예를 들어 "\(R\) 3"이라고 하면 오른쪽으로 3만큼 움직인 것이다.

최종적인 궤적을 살펴보면 다양한 다각형이 생겨난다. 이 다각형중에서 그 내부에 다른 점이나 선분을 포함하지 않은 사각형을 단순 사각형이라고 한다. 문제는 주어진 궤적으로 만들어진 단순 사각형 중에서 가장 작은 면적의 단순 사각형을 구하는 것이다.

위의 그림에서 촤표(4, 9)는 출발점이고 로봇의 움직인은 \(R\) 7, \(D\) 5, \(L\) 10, \(U\) 3, ... 으로 진행된다. 위 그림에서 회색으로 표시한 부분이 가장 작은 면적의 단순 사각형이므로 이것이 답이 된다.

두 선분이 만나는 경우는 수직선분과 수평선분이 한 점에서 만나는 경우 뿐이며 수평선분과 수평선분, 수직선분과 수직선분이 서로 만나거나 겹치는 경우는 없다.

첫째 줄에는 시작점의 \(x\)좌표와 \(y\)좌표가 하나의 빈칸을 사이에 두고 주어진다. 그 다음 줄에는 움직인 동작의 횟수 \(n\)이 주어진다. \(n\)은 100 이하의 정수이다. 그 다음 \(n\)개의 줄에는 움직임의 방향(\(U\), \(D\), \(R\), \(L\))과 거리가 하나의 빈칸을 사이에 두고 주어진다. 로봇의 움직임은 \(x\), \(y\) 모두 1 이상 100 이하의 정수 좌표 내에서 이루어진다.

가장 작은 면적을 갖는 단순 사각형의 왼쪽 아래 꼭짓점의 좌표를 첫째 줄에, 오른쪽 위 꼭짓점의 좌표를 둘째 줄에 출력하면 된다. 좌표의 출력은 \(x\)좌표, \(y\)좌표 순으로 하며 하나의 빈칸을 사이에 둔다. 가장 작은 면적의 단순 사각형이 여러 개인 경우에는 그 중에서 하나만 출력하면 된다. 만일 단순 사각형이 존재하지 않으면 첫째 줄에 0 을 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 1999 > 2차 대회 > 고등부 2번