BOJ 3972 Suiting Weavers

문제 링크:

문제 내용

어떤 개미 종류는 식물의 잎에서 나오는 섬유를 가지고 집을 짓습니다. 암컷 개미는 가장 큰 집을 지은 수컷 개미와 짝짓기를 합니다.

윌리를 포함한 $W$마리의 개미가 각자의 집을 지으려고 합니다. $i$번째 개미의 위치는 $(x_i, y_i)$이며, 그 개미의 집의 현재 크기(집을 구성하고 있는 섬유의 양)는 $f_i$입니다. 윌리는 1번째 개미입니다.

집의 재료가 되는 섬유는 $P$개의 위치에 흩어져 있습니다. $j$번째 장소의 위치는 $(X_j, Y_j)$이며, 그 장소에는 $F_j$만큼의 섬유가 있습니다.

각자의 개미는 그 개미가 다닐 수 있는 영역이 있습니다. 이 영역은 그 개미의 집을 중심으로 반지름 $r_i$인 원 모양이며, 그 개미는 자신의 영역 내부(테두리 포함)에 있는 섬유만 가져올 수 있습니다.

모든 개미가 집짓기를 완료했을 때, 윌리의 집보다 큰 집이 없을 가능성이 조금이라도 존재하는지 구하세요.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 100$)

각 테스트 케이스에 대해, 첫 번째 줄에는 $W$와 $P$가 주어집니다. ($1 \le W \le 100$, $1 \le P \le 400$)

다음 $W$줄에는 각각의 개미 $i$에 대해 $x_i$, $y_i$, $f_i$, $r_i$가 순서대로 한 줄에 주어집니다. ($0 \le x_i, y_i, r_i \le 10\;000$, $1 \le f_i \le 10\;000$)

다음 $P$줄에는 각각의 장소 $j$에 대해 $X_j$, $Y_j$, $F_j$가 순서대로 한 줄에 주어집니다. ($0 \le X_j, Y_j \le 10\;000$, $1 \le F_j \le 10\;000$)

출력

각 테스트 케이스에 대해, 윌리의 집보다 큰 집이 없을 가능성이 있다면 Suiting Success, 없다면 Lonesome Willy를 출력합니다.

문제 풀이