About ChainsawMassacre ¶
캐나다 벌목인 협회에서 최근에 연례 벌목 경진 대회를 개최했는데, 몬트리올과 뱅쿠버 사이에 있는 국립공원의 나무들이 많이 잘려나갔다. 경진 대회가 끝나고 벌목인들이 모두 모여 즐기기 위한 파티를 시작할 때가 되었다. 조직위원회에서는 이브닝 파티에 적합한 무도회장을 만들기 위해 나무가 한 그루도 없는 넓은 직사각형 모양의 공터를 찾고 있다. 벌목인들은 모두 술이 취해서 아무도 전기톱을 가지고 작업을 할 엄두를 못 내고 있다.
조직위원회에서 당신에게 무도회장으로 쓸 수 있는 가장 넓은 직사각형 영역을 찾아달라는 요청을 했다. 장소를 물색해야 할 전체 영역은 직사각형이며, 무도회장은 완전히 그 직사각형 안에 들어있어야 한다. 그리고 무도회장의 각 변은 전체 영역을 나타내는 직사각형의 각 변과 평행해야 한다. 무도회장은 주어진 영역의 경계에 닿아 있어도 된다. 그리고 무도회장 내부에만 나무가 없으면, 경계선 위에 나무가 있어도 상관없다.
Input ¶
첫째 줄에는 시나리오 개수가 입력된다. 각 시나리오의 첫째 줄에는 주어진 영역의 길이 l과 너비 w가 미터 단위로 입력된다(둘 다 정수며 0보다 크고 10,000 이하다). 그 밑으로는 각 줄마다 다음 형식에 따라 나무 한 그루 또는 한 줄로 심어진 나무들을 설명하는 내용이 입력된다.
- 1 × y - '1'은 나무가 한 그루라는 것을 의미하며, x와 y는 왼쪽 맨 위 지점을 기준으로 x와 y 좌표를 미터 단위로 표현한 것이다.
- k × y dx dy - k 가 1보다 크면 여러 그루의 나무가 한 줄로 심어져 있는 것을 나타내며, 그 좌표는 (x,y), (x+dx,y+dy),...,(x+(k-1)dx, y+(k-1)dy)이다.
- 0 - 시나리오가 끝났음을 의미한다.
