9039번 - 노선도 채점 준비 중

서울 시청 지하철노선 기획본부에 근무하는 공무원 미풍은 서울 지하철 노선도를 시민들이 최대한 보기 편하게 그리기를 원한다. 위 노선도에서는 분홍 원으로 표시되는 다섯 개의 역이 주어져 있다. 각각의 역은 고유 이름을 가지고 있다. 위 노선도에 나오는 역의 이름은 범계, 평촌, 인덕원, 정부과천청사, 과천이다. 미풍은 직사각형 형태의 이름표를 이용하여 각각의 역의 이름을 지도에 표시하기를 원한다. 각 이름표의 세로 크기는 같다고 가정한다. 이름표의 가로 크기는 이름의 길이에 정비례하여 정해진다. 이름표는 위 노선도와 같이 노선의 위 또는 아래에 노선과 접하게 그린다. 각 역의 이름표는 사용자가 최대한 보기 편하게 다음과 같은 좋은 조건 들을 만족시켜야 한다.

1. 각 역의 이름표는 그 역을 표시하는 원과 만나야 한다.
2. 각 역의 이름표는 다른 역을 나타내는 원과 접할 수는 있지만, 지나가서는 안 된다. 예를 들어, 위 노선도에서 정부과천청사 역의 이름표는 인덕원 역과 정부과천청사 역을 표시하는 원들과 접하고 있어서 괜찮지만, 아래 그림에서 정부과천청사 역의 이름표는 인덕원 역을 나타내는 원을 지나가고 있어서 안 된다. (각 역을 나타내는 원이 점인 경우에는 각 역을 표시하는 이름표의 어떤 변의 내부에 다른 역을 나타내는 점이 위치해서는 안 된다.)
3. 서로 다른 두 역의 이름표는 서로 접할 수는 있지만 겹쳐서는 안 된다.

위 세 조건을 만족시키는 노선도를 좋은 노선도 라 정의한다. 위의 그림은 좋은 노선도의 예이고 아래는 그렇지 않는 예이다.

길이가 무한한 직선으로 이루어진 하나의 지하철 노선에 대해 사용자가 보기 편한 좋은 노선도가 존재하는지를 판별하는 프로그램을 작성하시오. 또한 각 역을 나타내는 원은 하나의 점으로 표시된다고 가정한다.

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트케이스의 첫 줄에는 지하철역의 수 N (1 ≤ N ≤ 20)이 주어지고 그 다음 N 줄에 걸쳐 각 역의 일차원 좌표 x (0 ≤ x ≤ 1000), 그 역의 이름표의 가로 길이 r (0 < r ≤ 1000)가 정수로 주어진다. 각 역의 정보는 좌표값의 오름차순으로 주어진다. 각 정수 사이에는 하나의 공백이 있다.

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 좋은 노선도가 존재하면 YES, 그렇지 않으면 NO를 출력하시오.