問題
KTX 열차를 타고 학교로 돌아오면서도 열심히 문제를 풀던 A씨는 순간 창 밖을 내다보았다. KTX가 워낙 빠르다 보니 창밖의 풍경은 순식간에 지나가고 있었지만, 멀리 있는 물체들은 그렇게 빨리 지나가는 것처럼 보이지 않았다.
상황을 단순하게 하기 위해 2차원 좌표평면에서 열차와 전봇대만으로 구성된 문제를 고려하자. 점으로 고려할 수 있는 열차가 x 축에 난 철로를 따라 x = ∞ 인 점에서부터 출발하여 x = 1인 지점까지 전진한다. 이 열차가 지나감에 따라 열차 안에 있는 A씨의 시야에서는 전봇대들이 나타났다 사라졌다 할 것이다.
A씨는 열차의 우측 창쪽 자리에 앉았으므로 y＞0 인 영역 중 좌우로 45도를 볼 수 있다. 구체적으로, 열차의 진행 방향에 대해 반시계방향으로 45°에서 135°까지의 영역을 볼 수 있다. 이 영역에서 벗어나는 전봇대는 볼 수 없다.
A씨는 특정 순간에 사진을 찍어 가장 많은 전봇대가 화면에 나오게 하고 싶다. 그런데 전봇대는 세로로 길쭉한 물체이기 때문에 어떤 순간에서는 두 전봇대가 열차의 시선에서 겹쳐 보일 수 있다. 이러한 전봇대는 하나만 보이는 것으로 생각하자. 또한 시야의 양쪽 경계에 걸리는 것은 모두 안쪽에 포함시키기로 하자. 사진에 최대 몇 개의 전봇대를 담을 수 있는가?
入力
첫 행에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 행에는 전봇대의 수 N (1≤N≤1,000) 가 주어진다. 다음 N개의 행에 걸쳐 각 전봇대의 정수 좌표 x, y (0＜x, y＜1,000)가 공백으로 구분되어 주어진다.
出力
테스트 케이스 하나당 한 행씩 순서대로 가능한 최대 전봇대의 수를 출력한다.
例題
1
6
10 1
17 7
35 5
40 8
73 6
85 3
2
ログインしないとコードを書けません。