레이저 선

한 컴퓨터 칩 제조사가 광전자 소자와 일반 전자 소자를 결합하는 새로운 방법을 찾아냈다. 칩 표면에 빛을 내보내는 노드와 받아들이는 노드를 배치하는 방식이다. 노드들은 서로 직선 시야(line of sight)를 따라 메시지를 주고받으며, 덕분에 훨씬 높은 밀도로 정보를 전송할 수 있어 동작 속도가 크게 빨라진다.

문제는 모든 노드가 다른 모든 노드에게 메시지를 보낼 수 있어야 한다는 점이다. 즉, 어떤 노드도 다른 두 노드 사이의 시야를 가로막아서는 안 된다. 제조 공정상 각 노드는 칩을 덮는 격자의 격자점 위에 정확히 놓이므로, 좌표는 0 이상 9999 이하의 정수 쌍으로 주어진다. 단, 기술적인 이유로 어떤 노드도 점 (0, 0)에는 놓이지 않는다.

여러 개의 노드 좌표 집합을 입력받아, 각 집합마다 세 개 이상의 노드를 지나는 직선 위에 놓인 노드가 있는지 판정하는 프로그램을 작성하라. 세 개의 노드를 지나는 직선은 여러 개 나타날 수 있지만, 더 긴 직선은 점점 드물어진다. 어떤 직선도 10개를 넘는 노드를 포함하지 않는다.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 집합은 3개 이상 300개 이하의 점 좌표를 담는다. 좌표는 0 이상 9999 이하의 정수 쌍이며, 각 집합은 정수 쌍 0 0으로 끝난다. 수들은 하나 이상의 공백으로 구분되고, 한 집합이 여러 줄에 걸쳐 나뉘어 주어질 수도 있다. 줄바꿈은 항상 좌표 쌍과 쌍 사이에서만 일어나며, 한 쌍을 이루는 두 수 사이에서는 절대 일어나지 않는다. 마지막 데이터 집합 뒤에는 전체 입력의 끝을 나타내는 정수 쌍 0 0이 한 번 더 주어진다. 데이터 집합은 여러 개이지만, 그중 100개를 초과하는 점을 담는 집합은 단 하나뿐이다.

각 데이터 집합마다 다음 중 하나를 정확히 출력한다.

• 세 개 이상의 점을 지나는 직선이 하나도 없으면 No lines were found을 출력한다.
• 그런 직선이 있으면 The following lines were found: (끝에 공백 한 칸 포함)을 출력한 뒤, 세 개 이상의 점을 지나는 각 직선마다 한 줄씩 출력한다.

각 직선의 줄에는 그 직선 위에 놓인 점들을 x좌표 기준 오름차순으로, x좌표가 같으면 y좌표 기준 오름차순으로 정렬해 나열한다. 각 좌표는 폭 4의 자리(오른쪽 정렬, 공백으로 채움)에 출력하고, 한 점의 두 좌표는 쉼표로 구분하여 괄호로 감싼다(한 점은 예를 들어 ( 4, 8) 형태). 연속한 점들은 사이에 공백 없이 바로 이어 붙인다. 여러 직선의 출력 순서도 각 직선 위 점들의 정렬 방식과 같다. 먼저 각 직선의 첫 번째 점을 기준으로 정렬하고, 첫 번째 점이 같은 직선이 여러 개이면 두 번째 점을, 그다음 점을 차례로 기준으로 삼아 순서를 정한다.