시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 14 11 52.381%

문제

두 개의 직선을 나타내는 4개의 점이 입력으로 주어질 때, 두 직선이 만나는지를 확인하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 N이 주어진다. (N <= 10)

다음 N개의 줄에는 각각 8개의 정수 x1, y1, x2, y2, x3, y3, x4, y4가 주어진다. 이는 두 직선 (x1, y1)-(x2, y2)와 (x3, y3)-(x4, y4)를 나타낸다.

(x1, y1)과 (x2, y2)는 서로 다른 점이며, (x3, y3)와 (x4, y4)는 서로 다른 점임이 보장된다.

모든 x와 y는 [-1000, 1000] 범위 내의 정수이다.

출력

각각의 테스트 케이스에 대해, 다음과 같이 출력한다.

  • 두 직선이 정확히 한 점에서 만난다면, POINT x y의 꼴로 출력한다. 이는 두 직선이 (x,y)에서 교차함을 의미한다. x와 y는 정확히 소숫점 아래 둘째 자리까지 출력한다.
  • 두 직선이 만나지 않는다면, NONE을 출력한다.
  • 두 직선이 무한히 많은 점에서 만난다면,  LINE을 출력한다.

원문에 있는 INTERSECTING LINES OUTPUT/END OF OUTPUT 등은 출력하지 않는다.

예제 입력

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

예제 출력

POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20

힌트