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

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

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

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

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

#1224 upload 24 done 6 how_to_reg 6

단순사각형 timer 1s memory 128MB

#1224

단순사각형 1s 128MB