| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 102 | 60 | 59 | 67.045% |
마왕 박상훈은 약육강식의 세계인 마계의 정점에 군림하고 있는, 마계의 최강자이다. 박상훈은 마계가 지루해진 나머지, 좌표평면을 침략하여 지배하고자 한다! 이를 위해 박상훈은 총 $N$개의 마법진을 준비하였다. 이중 $i$번 마법진은 좌표평면에서 $(x_i-r_i,y_i-r_i)$와 $(x_i+r_i,y_i+r_i)$를 대각선의 양쪽 꼭짓점으로 하는 정사각형 내부를 섬멸하는 마법진이다. 정사각형의 경계는 마법진의 범위에 속하지 않음에 주의하라. 박상훈은 이 마법진들 중 일부를 선택하고, 이들만을 사용하여 좌표평면을 공격할 것이다. 이 공격의 위력은, 마법진들의 범위의 합집합의 면적으로 정의된다.
박상훈은 검소한 왕이기 때문에, 두 개 이상의 서로 다른 마법진이 동일한 장소를 공격하는 것은 큰 낭비라고 생각한다. 따라서 좌표평면 위의 어떠한 점도, 박상훈이 선택한 마법진 중 최대 하나의 범위에만 포함되어야만 한다.
박상훈은 위대한 왕이기 때문에, 박상훈이 진행하는 공격은 매우 강력해야 한다. 따라서 박상훈이 고른 마법진들을 사용하는 공격의 위력은, 준비된 모든 마법진들을 사용하는 공격의 위력의 $\frac{1}{9}$배 이상이어야 한다.
박상훈은 바쁜 왕이기 때문에, 위의 조건을 만족하도록 마법진을 선택하기 위해 쓸 시간이 없다. 마왕 박상훈의 성공적인 좌표평면 침략을 위해, 당신이 어떤 마법진을 선택해야 하는지 알려주자.
첫 번째 줄에 양의 정수 $N$이 주어진다.
이후 $N$개의 줄에 걸쳐 세 정수 $x_i,y_i,r_i$가 공백으로 구분되어 주어진다. 이는 $i$번 마법진의 범위가 $(x_i-r_i,y_i-r_i)$와 $(x_i+r_i,y_i+r_i)$를 대각선의 양쪽 꼭짓점으로 하는 정사각형 내부임을 의미한다.
항상 조건을 만족하는 마법진의 선택이 한 가지 이상 존재하는 경우만 입력으로 주어진다.
첫 번째 줄에 마법진의 개수를 의미하는 $N$ 이하의 양의 정수 $M$을 출력한다.
이후 $M$개의 줄에 걸쳐 정수 $k_i$를 출력한다. 이는 공격에 사용할 마법진의 번호를 나타낸다
9 -5 -5 3 -5 0 3 -5 5 3 0 -5 3 0 0 3 0 5 3 5 -5 3 5 0 3 5 5 3
4 1 3 7 9
Contest > BOJ User Contest > Good Bye, BOJ > Good Bye, BOJ 2025! C번