두 직선의 교차 여부

면접 대비

시간 제한1초메모리 제한128 MB

요약
두 정수 점으로 정의된 두 직선이 한 점에서 만나는지, 평행한지, 일치하는지 판별하고 교점을 소수 둘째 자리까지 출력한다.
난이도

보통10점 중 4점

유형
기하, 수학, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

두 직선을 나타내는 네 점이 주어질 때, 두 직선이 서로 어떻게 놓여 있는지를 판별하는 프로그램을 작성하시오. 두 직선은 한 점에서 만나거나, 서로 만나지 않거나(평행), 완전히 겹칠 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 NN이 주어진다. (1≤N≤101 \le N \le 10)

이어지는 NN개의 줄에는 각 줄마다 정수 여덟 개 x1 y1 x2 y2 x3 y3 x4 y4x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4가 주어진다. 이는 점 (x1,y1)(x_1, y_1)과 (x2,y2)(x_2, y_2)를 지나는 첫 번째 직선과, 점 (x3,y3)(x_3, y_3)과 (x4,y4)(x_4, y_4)를 지나는 두 번째 직선을 나타낸다.

(x1,y1)(x_1, y_1)과 (x2,y2)(x_2, y_2)는 서로 다른 점이고, (x3,y3)(x_3, y_3)과 (x4,y4)(x_4, y_4)도 서로 다른 점임이 보장된다.

모든 좌표는 −1000-1000 이상 10001000 이하의 정수이다.

출력

각 테스트 케이스마다 다음 규칙에 따라 한 줄씩 출력한다.

  • 두 직선이 정확히 한 점 (x,y)(x, y)에서 만나면 POINT x y 형식으로 출력한다. 이때 xx와 yy는 각각 반올림하여 소수점 아래 둘째 자리까지 출력한다.
  • 두 직선이 만나지 않으면(평행하고 겹치지 않으면) NONE을 출력한다.
  • 두 직선이 완전히 겹쳐 무수히 많은 점에서 만나면 LINE을 출력한다.

INTERSECTING LINES OUTPUT나 END OF OUTPUT 같은 머리말·꼬리말은 출력하지 않는다.

예제1

  1. 예제 1

    입력
    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