9074번 - 쇠줄 곧게 펴기 채점 준비 중

P 제철 회사에 문제가 생겼다. 작업공정의 문제로 반듯했던 쇠줄의 곳곳에 직각으로 꺾인 부분이 생긴 것이다. 고로 쇠줄을 다시 반듯하게 펴야 하는 작업을 해야 한다. 한 번에 쇠줄의 마디 한 곳만을 펼 수 있으며 펴는 도중에 쇠줄 내에서 충돌이 생겨서도 안 된다. 한 점에서만 충돌이 일어나도 충돌인 것으로 간주한다. 마디를 '편다'는 것은 그 마디를 포함한 양 변이 일직선으로 되는 것을 의미한다. 쇠줄을 펼 때는 한 쪽 끝에서 시작해서 연결된 순서대로 마디를 펴는 것으로 하고 시작되는 한 쪽 끝은 입력으로 주어진다. 아래 예제는 2차원 평면에 아래와 같이 쇠줄이 주어져 있을 때 한쪽 끝에서 시작해서 연결된 순서대로 마디를 펴서 최종적으로 직선으로 곧게 편 형태이다. 

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 한 줄에 쇠줄의 각 끝점을 포함한 마디의 개수가 주어지고 다음 줄에는 각 끝점을 포함한 마디의 점의 x, y 좌표들이 한 쪽 끝의 좌표부터 연결된 순서대로 공백을 하나씩 두고 주어진다. 각 좌표는 정수 값(0 ≤ x ≤ 1000, 0 ≤ y ≤ 1000)을 갖는다. 또한 총 쇠줄의 길이는 10000을 넘지 않고 좌표의 개수는 1000을 넘지 않는다. 쇠줄은 처음 주어진 좌표 순서대로 각 마디를 펴는 것으로 한다. 펴진 후에 좌표는 제한되지 않는다. 그리고 입력 자체에 아무 것도 펴지 않은 상태에서 충돌은 없다. 또한, 입력에 직각으로 꺾이지 않은 마디의 좌표는 없는 것으로 한다. 

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해 주어진 점의 좌표 순서대로 마디를 폈을 때 최종적으로 직선으로 펼 수 있으면 YES, 그렇지 않으면 NO를 각 테스트케이스에 대해 한 줄에 하나씩 출력한다.