레이팅 미적용설명
농부 존의 소 N마리의 (1 <= N <= 500) 위치가 2차원 평면 위의 서로 다른 점들로 주어진다. 소는 홀스타인과 건지의 두 품종으로 나뉜다. 농부 존은 좌표축에 평행한 변을 가진 직사각형 울타리를 세워 홀스타인만 가두고 건지는 한 마리도 포함하지 않으려 한다 (경계 위에 있는 소도 울타리 안에 있는 것으로 간주한다). 그러한 울타리들 중에서 홀스타인을 최대한 많이 가두고 싶고, 그중에서도 넓이가 최소인 울타리를 원한다. 이 넓이를 구하시오. 폭이나 높이가 0인 울타리도 허용된다.
제약
입력 형식
첫째 줄에 N이 주어진다.
다음 N개의 줄 각각에는 소 한 마리를 나타내는 두 정수와 문자 하나가 주어진다: 점 (x,y) (0 <= x,y <= 1000)와 품종 H 또는 G이다. 같은 점에 있는 소는 없으며, 홀스타인은 항상 최소 한 마리 존재한다.
출력 형식
두 정수를 출력한다: 건지를 포함하지 않는 울타리로 가둘 수 있는 홀스타인의 최대 수와, 그러한 울타리로 둘러싸이는 최소 넓이이다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
cowrect.in · 출력을 쓸 파일 cowrect.out예제 1
입력
5
1 1 H
2 2 H
3 3 G
4 4 H
6 6 H출력
2
1문제 정보
태그