#1766 엉터리 회귀분석

21  1 s   128 MB  

Description

최근 확률과 통계 2 과목을 듣고 있는 재연이는 회귀분석법을 수강하고 있고, 지금까지 공부한 내용을 토대로 지금까지 들었던 과목들에 대해 공부한 시간과 성적의 상관관계를 회귀분석을 하려고 한다.

하지만 최소 자승법(least square method)를 제대로 공부하지 않은 재연이는 머리를 짜내어 다음과 같은 방법으로 회귀분석을 하고자 한다. 우선 각 과목을 2차원 좌표의 점으로 간주하고, 각 과목에 대해서 공부한 시간을 x좌표, 얻은 성적을 y좌표로 간주를 한다음 2차원 평면에 점을 찍은 다음, 평면에 임의의 직선을 긋는데 최대한 많은 점이 포함되게 긋고자 한다.
재연이는 다음과 같은 프로그램을 작성을 하였는데, 왠지 급하게 짠 것 같은 감이 있어서 친한 친구인 당신에게도 프로그램을 짜게 하여 프로그램이 제대로 돌아가는지 확인하고자 한다.

Input

 

입력은 여러개의 테스트 케이스로 이루어지며 첫 줄에는 이하의 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 입력된다.
각 테스트 케이스에는 정수 N 이 입력되며( 1 ≤ N ≤ 100 ), 이는 재연이가 기록한 각 과목의 공부시간과 성적의 개수를 뜻한다.
그 다음줄 부터 N 개의 줄에는 재연이가 기록한 각 과목의 공부시간을 뜻하는 e와 해당 과목에서 받은 점수인 s가 정수의 형태로 입력되며, 동일한 e, s 값이 중복되어 입력되는 경우는 없다고 가정한다( 0 ≤ s, e ≤ 100 ).

Output

각 테스트 케이스에 대해 임의의 직선을 그었을 때 포함 되는 최대 점의 개수를 출력한다.

Sample Input

Sample Output

3
4
1 1
2 2
3 3
4 4
4
1 2
2 3
3 4
4 5
3
1 1
2 2
3 5
4
4
2

Source

2011 Ajou University Programming Contest, Division 1