| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 310 | 181 | 120 | 62.500% |
자취하게 된 코더빡은 기뻐하는 것도 잠시, 자취방이 너무 좁아 그가 보유하고 있는 엄청난 양의 전자기기들을 다 들여놓지 못할 것 같다는 불안감에 휩싸였다. 하지만 그는 뛰어난 공간 감각을 활용해 모든 전자기기를 방 안에 넣었다! 그 후, 그는 가만히 있는 상태에서 최대 몇 개의 전자기기가 손에 닿을 수 있는지 궁금해졌다.
그는 전자기기 $N$개를 가지고 있으며 각각의 전자기기는 직사각형 모양이다. 그는 원점 $(0, 0)$에 있으며 팔의 길이는 $R$이기 때문에, 어떤 전자기기의 일부분과 원점 $(0, 0)$ 사이의 거리가 $R$ 이하라면 해당 전자기기는 그의 손에 닿는다. 전자기기는 서로 겹칠 수 있으며 전자기기 내부에 원점 $(0, 0)$이 포함된다면 역시 손에 닿는다고 간주한다.
또한 그는 각 전자기기의 무게 중심을 고정한 채 전자기기를 자유롭게 회전시킬 수 있다. 최적의 형태로 회전시켰을 때 최대 몇 개의 전자기기가 코더빡의 손에 닿는지 계산해 보자.
첫 번째 줄에 전자기기의 수 $N,ドル 코더빡의 팔의 길이 $R$이 공백으로 구분되어 주어진다.
두 번째 줄부터 $N$개의 줄에 걸쳐 전자기기의 정보가 주어진다. 그중 $i$번째 줄에는 $x_{i1},ドル $y_{i1},ドル $x_{i2},ドル $y_{i2},ドル $x_{i3},ドル $y_{i3},ドル $x_{i4},ドル $y_{i4}$가 공백으로 구분되어 주어진다. 이는 네 꼭짓점 $(x_{i1}, y_{i1}),ドル $(x_{i2}, y_{i2}),ドル $(x_{i3}, y_{i3}),ドル $(x_{i4}, y_{i4})$으로 이루어진 직사각형 모양의 전자기기를 의미한다. 이때 꼭짓점의 좌표는 시계 방향 순서대로 주어진다.
첫 번째 줄에 손에 닿는 전자기기의 최대 개수를 출력한다.
5 5 0 0 0 1 1 1 1 0 -4 3 4 3 4 -3 -4 -3 0 6 1 6 1 4 0 4 5 0 5 1 6 1 6 0 4 5 5 6 7 4 6 3
4
University > Centroid 연합 > 2024 국민대학교 & 중앙대학교 연합 프로그래밍 경진대회 D번