인기도:C(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)
About ChocolateChipCookies ¶
초코칩 쿠키를 만들기 위해 밀가루와 소금, 기름, 베이킹 소다, 초콜릿 칩을 섞어서 반죽을 만든 다음 가로, 세로 50cm의 정사각형 모양으로 밀어서 편다. 그리고 이 평평한 반죽을 원형으로 잘라서 쿠키판 위에 놓은 다음 약 20분 동안 오븐에서 굽는다. 쿠키가 다 되고 나면 오븐에서 꺼내서 식힌다.
반죽을 밀어서 편 다음에 첫번째 쿠키를 잘라내는 단계를 생각해보자. 반죽에 들어있는 초콜릿 칩은 모두 겉으로 드러나 있는데, 원 안에 칩이 최대한 많이 들어갈 수 있도록 자르는 방법을 찾아보자.
Input ¶
첫째 줄에는 테스트 케이스의 개수를 나타내는 양의 정수가 한 개 입력된다. 그 다음 줄은 빈 줄이며, 서로 다른 테스트 케이스는 빈 줄로 구분된다.
각 테스트 케이스마다 여러 줄이 입력되는데, 각 줄마다 쿠키 반죽의 정사각형 표면에 있는 칩의 위치인 (x,y) 좌표를 나타내는 부동소수점수가 두 개씩 입력된다. 각 좌표는 0.0 이상 50.0 이하다. (단위는 센티미터) 각 칩은 점으로 생각할 수 있다. 초콜릿 칩의 개수는 최대 200개며, 전부 서로 다른 위치에 있다.
각 테스트 케이스마다 여러 줄이 입력되는데, 각 줄마다 쿠키 반죽의 정사각형 표면에 있는 칩의 위치인 (x,y) 좌표를 나타내는 부동소수점수가 두 개씩 입력된다. 각 좌표는 0.0 이상 50.0 이하다. (단위는 센티미터) 각 칩은 점으로 생각할 수 있다. 초콜릿 칩의 개수는 최대 200개며, 전부 서로 다른 위치에 있다.
Output ¶
각 테스트 케이스에 대해 지름 5cm인 쿠키 한 개에 들어갈 수 있는 초콜릿 칩의 최대 개수를 나타내는 정수를 하나씩 출력한다. 쿠키가 완전히 가로, 세로 50cm인 반죽 판 안에 들어가야 할 필요는 없다(즉 쿠키가 완전히 원 모양이 아니어도 괜찮다).
서로 다른 테스트 케이스의 결과 사이에는 빈 줄을 출력한다.
서로 다른 테스트 케이스의 결과 사이에는 빈 줄을 출력한다.
Sample Input ¶
{{| 1
4.0 4.0
4.0 5.0
5.0 6.0
1.0 20.0
1.0 21.0
1.0 22.0
1.0 25.0
1.0 26.0 |}}
4.0 5.0
5.0 6.0
1.0 20.0
1.0 21.0
1.0 22.0
1.0 25.0
1.0 26.0 |}}
Sample Output ¶
{{| 4 |}}
