레이 라인
시간 제한15초메모리 제한2048 MB
세 점이 한 직선 위에 있지 않은 n개의 점과 연필 두께 t가 주어질 때, 너비 t인 띠 하나로 덮을 수 있는 점의 최대 개수를 구한다.
문제
1921년, 아마추어 고고학자 앨프리드 왓킨스는 지리적, 역사적으로 흥미로운 수많은 장소를 잇는 직선을 가리키는 말로 "레이 라인"이라는 용어를 만들었다. 이 선들은 종종 신비롭고 신비주의적인 이론과 연결되었고, 그중 상당수는 지금도 남아 있다.
레이 라인에 대한 흔한 비판 중 하나는 지도 위에 그리는 선은 실제로 폭이 0이 아니며, 점의 밀도가 충분히 높고 연필이 충분히 굵다면 여러 장소를 잇는 "선"을 찾는 일은 trivial하다는 것이다. 이 문제에서는 그 비판을 살펴본다.
단순화를 위해 지구의 곡률은 무시하고, 평면 위의 점 집합을 다룬다고 가정한다. 각 점은 고유한 (x, y) 좌표를 가지며, 어떤 세 점도 한 직선 위에 있지 않다. 그러한 집합과 연필의 굵기가 주어졌을 때, 하나의 선으로 지나갈 수 있는 점의 최대 개수는 몇 개인가?
입력
입력의 첫 줄은 두 정수 n과 t로 이루어진다. n (3 ≤ n ≤ 3 000)은 집합의 점 개수이고, t (0 ≤ t ≤ 109)는 연필의 굵기이다. 이어서 n개의 줄이 주어지며, 각 줄은 집합에 속한 한 점의 좌표를 나타내는 두 정수 x와 y (−109 ≤ x, y ≤ 109)를 포함한다.
입력은 굵기 t를 10−2만큼 늘리거나 줄여도 답이 변하지 않는 경우이며, 어떤 세 입력 점도 한 직선 위에 있지 않다고 가정해도 된다.
출력
굵기 t인 하나의 "선" 위에 있는 점의 최대 개수를 출력한다.