문제
주얼리 전시장에서는 세계적인 예술가들이 제작한 보석을 전시할 예정이다. 야간이나 휴무일 일 때 일어날 수 있는 도난 방지를 위하여 전시장의 보안 담당자는 레이저 감시 장치를 설치하기로 하였다. 하지만 감시 장치가 비싸므로 모든 보석을 감시하면서도 가능한 적은 수의 장치를 사용해야 한다.
레이저 감시 장치는 발신기와 수신기가 한 세트로 이루어져 있다. 감시 장치 한 세트는 너비 1단위 구간을 감시할 수 있으며 빛의 길이는 100단위까지 가능하다. 반드시 양쪽 벽에 설치해야 하며 발신 장치와 수신 장치가 평행한 상태에서 정확히 서로 마주 보고 있어야 한다. 또한 이 장치는 정수 좌표에 있는 보석을 감시하지 못하는데 다행히도 전시되는 보석은 정수가 아닌 실수 좌표에 있다.
전시장은 R개의 방으로 구성되며 각 방은 직사각형 모양이고 방의 내부에는 기둥이나 벽이 존재하지 않고 보석들만 있다.
아래 그림은 입력 예의 두 번째 방을 그린 것이다.
여덟 개의 보석이 있으며 8개 세트의 레이저 감시 장치를 사용할 수도 있지만 오른쪽 그림처럼 3개만으로도 가능하다.
입력
첫 행에 방의 개수 R( 1 ≤ R ≤ 10)이 입력된다.
이후 R개의 방에 대한 정보가 입력되는데, 방 정보의 첫 행에는 방의 가로와 세로를 나타내는 두 정수 N, M ( 0 < N, M ≤100)과 보석의 개수를 나타내는 K ( 0 < K ≤ 10000)가 공백으로 구분되어 입력된다.
이어 K개의 행에 보석의 위치를 나타내는 Xi, Yi가 ( 0 < Xi <N, 0 < Yi < M) 정수가 아닌 실수 값으로 주어진다.
출력
각 방에 대하여 모든 보석을 감시하면서 가능한 적은 수의 레이저 감시 장치 세트를 사용할 때 세트수를 행으로 구분하여 출력한다.
예제
2
1 5 3
0.2 1.5
0.3 4.8
0.4 3.5
4 4 8
0.7 0.5
1.7 0.5
2.8 1.5
3.7 0.5
2.2 3.6
2.7 2.7
1.2 2.2
1.2 2.7
1
3
출처
GCPC 2014
로그인해야 코드를 작성할 수 있어요.