초콜릿 칩 쿠키
시간 제한1초메모리 제한128 MB
최대 200개의 점이 주어질 때, 반지름 2.5cm인 원 안에 들어갈 수 있는 점의 최대 개수를 구한다. 원이 반죽 경계를 넘어가도 된다.
문제
초콜릿 칩 쿠키를 만들려면 밀가루, 소금, 기름, 베이킹 소다, 초콜릿 칩을 섞어 반죽을 만들고, 이 반죽을 약 50 cm 정사각형 크기의 평평한 판으로 밀어 편다. 이 판에서 원을 잘라내 굽는 판에 올린 뒤 약 20분 동안 굽는다.
여기서는 반죽을 밀어 편 뒤 첫 번째 쿠키를 잘라내는 과정만 다룬다. 모든 초콜릿 칩은 평평한 반죽 위에서 보이므로, 원형 커터를 놓아 그 안에 들어오는 초콜릿 칩의 개수가 최대가 되도록 하기만 하면 된다.
입력
입력은 여러 줄로 이루어진다. 각 줄에는 반죽의 정사각형 표면 위에 있는 칩 하나의 좌표를 나타내는 두 실수가 들어 있다. 각 좌표는 이상 이하이다(단위는 cm). 각 칩은 하나의 점으로 간주하며, 두 칩이 같은 위치에 있는 경우는 없다. 칩의 개수는 최대 개이다.
출력
정수 하나를 출력한다. 지름이 cm인 원형 쿠키 하나 안에 들어올 수 있는 초콜릿 칩의 최대 개수이다. 자르는 원의 경계선 위에 정확히 놓인 칩도 포함된 것으로 센다. 커터가 cm 정사각형 반죽 안에 완전히 들어갈 필요는 없으며, 반죽의 가장자리를 넘어가도 된다(그래서 쿠키의 한쪽이 잘려 평평해질 수 있다).