오염물질 제거하기 - 구름LEVEL
오염물질 제거하기
Quiz Info
오염물질 제거하기
100points
Participant
8
Solved Rate
12.5%
3
0
 지난 가을 한 나라에서는 많은 폐기물이 바다로 흘러내려가는 사건이 발생했다. 폐기물의 회수작업이 지연되자 많은 폐기물들은 먼 바다로 흘러가게되었다. 심각한 해양 오염을 걱정한 주변국들은 단결하여 바다로 나온 폐기물들을 제거하려고 한다.

 모든 폐기물을 일일이 선박을 사용해 인양하는 것은 불가능에 가까웠기 때문에 많은 나라들은 폐기물의 수를 줄일 방법을 고민하게 된다. 당신은 마침 개발이 완료된 레이저 분쇄기를 사용해 최대한 많은 폐기물을 제거할 방법을 세워야 한다. 레이저 분쇄기는 강력한 레이저를 일직선으로 발사해 마주치는 모든 폐기물을 파괴할 수 있는 장비다. 하지만 레이저 분쇄기는 아직 불안전하기 때문에 단 한번만 사용할 수 있다.

그림 1. 첫 번째 예제 데이터를 좌표계에 표시한 예시. l1과 같은 방향으로 레이저 분쇄기를 사용하면 네 개의 폐기물을 제거할 수 있다. 다른 방법들도 가능하지만, 네 개 보다 많은 폐기물을 제거할 수 있는 방법은 존재하지 않는다. 이 경우 정답은 4가 된다.


 위의 그림과 같이 인공위성으로 촬영된 N개의 폐기물의 위치 정보가 입력으로 주어진다. 각 폐기물의 위치는 2차원 좌표계의 한 점으로 표현된다. 편의상 폐기물의 크기는 신경쓰지 않는다. 정확히 폐기물이 위치하는 점을 지나는 방향으로 레이저 분쇄기를 사용해야만 해당 폐기물을 제거할 수 있다. 

 당신은 위치와 방향을 자유롭게 선택해 레이저 분쇄기를 사용할 수 있다. 레이저 분쇄기는 해당 방향으로 무한히 진행하며 정확히 교차하는 폐기물만을 파괴한다. 각 폐기물들의 위치가 입력으로 주어질 때, 한 번의 레이저 분쇄기의 사용으로 제거할 수 있는 가장 많은 폐기물의 수를 계산하는 프로그램을 작성하시오.


입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 1이상 20이하의 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 차례로 주어진다.

 각 테스트케이스의 첫 줄에는 폐기물의 수를 나타내는 1이상 1,000이하의 자연수 N이 주어진다. 이후 총 N개의 폐기물에 대한 2차원 좌표가 주어진다.

 각 폐기물의 좌표는 공백으로 구분 된 두 개의 정수가 X Y 형식으로 주어진다.

  • 모든 폐기물은 서로 다른 좌표를 가진다.
  • 모든 좌표값은 절대값이 1억 이하인 정수다.


출력 형식

 각 테스트케이스에 대한 정답을 한 줄마다 출력한다.

  • 한 번의 레이저 사용으로 제거할 수 있는 최대의 폐기물 수를 정수로 출력한다.
Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
1
10
41
91
56
28
18
75
94
110
51
85
Output
4
Example 2
Input
2
5
13
46
810
21
52
5
59
13
68
25
52
Output
3
2
⋇ Please keep the input and output formats carefully
Q & A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다.
다른 수강생들과 질문과 답변을 주고 받으며 함께 성장하세요!

Registered Questions (0)