시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 167 54 40 48.193%

문제

두 개의 직선을 나타내는 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 등은 출력하지 않는다.

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

예제 출력 1

POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
W3sicHJvYmxlbV9pZCI6IjY0ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzU4IFx1YWQ1MFx1Y2MyOCBcdWM1ZWNcdWJkODAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjOWMxXHVjMTIwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCA0XHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHViNDUwIFx1YzljMVx1YzEyMFx1Yzc3NCBcdWI5Y2NcdWIwOThcdWIyOTRcdWM5YzBcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChOICZsdDs9IDEwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIDhcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHgxLCB5MSwgeDIsIHkyLCB4MywgeTMsIHg0LCB5NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWI0NTAgXHVjOWMxXHVjMTIwICh4MSwgeTEpLSh4MiwgeTIpXHVjNjQwICh4MywgeTMpLSh4NCwgeTQpXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+KHgxLCB5MSlcdWFjZmMgKHgyLCB5MilcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4MTBcdWM3NzRcdWJhNzAsICh4MywgeTMpXHVjNjQwICh4NCwgeTQpXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODEwXHVjNzg0XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIHhcdWM2NDAgeVx1YjI5NCBbLTEwMDAsIDEwMDBdJm5ic3A7XHViYzk0XHVjNzA0IFx1YjBiNFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzc0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHVjODEwXHVjNWQwXHVjMTFjIFx1YjljY1x1YjA5Y1x1YjJlNFx1YmE3NCwgUE9JTlQgeCB5XHVjNzU4IFx1YWYzNFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzc0ICh4LHkpXHVjNWQwXHVjMTFjIFx1YWQ1MFx1Y2MyOFx1ZDU2OFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIHhcdWM2NDAgeVx1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVjMThjXHVjMjJiXHVjODEwIFx1YzU0NFx1Yjc5OCBcdWI0NThcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YzljMVx1YzEyMFx1Yzc3NCBcdWI5Y2NcdWIwOThcdWM5YzAmbmJzcDtcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQsIE5PTkVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHVjOWMxXHVjMTIwXHVjNzc0IFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWI5Y2VcdWM3NDAgXHVjODEwXHVjNWQwXHVjMTFjIFx1YjljY1x1YjA5Y1x1YjJlNFx1YmE3NCwmbmJzcDsgTElORVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNmQwXHViYjM4XHVjNWQwIFx1Yzc4OFx1YjI5NCZuYnNwO0lOVEVSU0VDVElORyBMSU5FUyBPVVRQVVRcL0VORCBPRiBPVVRQVVQgXHViNGYxXHVjNzQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjQ4NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkludGVyc2VjdGluZyBMaW5lcyIsImRlc2NyaXB0aW9uIjoiPHA+V2UgYWxsIGtub3cgdGhhdCBhIHBhaXIgb2YgZGlzdGluY3QgcG9pbnRzIG9uIGEgcGxhbmUgZGVmaW5lcyBhIGxpbmUmbmJzcDthbmQgdGhhdCBhIHBhaXIgb2YgbGluZXMgb24gYSBwbGFuZSB3aWxsIGludGVyc2VjdCBpbiBvbmUgb2YgdGhyZWUmbmJzcDt3YXlzOiAxKSBubyBpbnRlcnNlY3Rpb24gYmVjYXVzZSB0aGV5IGFyZSBwYXJhbGxlbCwgMikgaW50ZXJzZWN0IGluIGEmbmJzcDtsaW5lIGJlY2F1c2UgdGhleSBhcmUgb24gdG9wIG9mIG9uZSBhbm90aGVyIChpLmUuIHRoZXkgYXJlIHRoZSBzYW1lJm5ic3A7bGluZSksIDMpIGludGVyc2VjdCBpbiBhIHBvaW50LiAmbmJzcDtJbiB0aGlzIHByb2JsZW0geW91IHdpbGwgdXNlIHlvdXImbmJzcDthbGdlYnJhaWMga25vd2xlZGdlIHRvIGNyZWF0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIGhvdyBhbmQmbmJzcDt3aGVyZSB0d28gbGluZXMgaW50ZXJzZWN0LjxcL3A+XHJcblxyXG48cD5Qcm9ibGVtIFN0YXRlbWVudDogWW91ciBwcm9ncmFtIHdpbGwgcmVwZWF0ZWRseSByZWFkIGluIGZvdXImbmJzcDtwb2ludHMgdGhhdCBkZWZpbmUgdHdvIGxpbmVzIGluIHRoZSB4LXkgcGxhbmUgYW5kIGRldGVybWluZSBob3cgYW5kJm5ic3A7d2hlcmUgdGhlIGxpbmVzIGludGVyc2VjdC4gJm5ic3A7QWxsIG51bWJlcnMgcmVxdWlyZWQgYnkgdGhpcyBwcm9ibGVtJm5ic3A7d2lsbCBiZSByZWFzb25hYmxlLCBzYXkgYmV0d2VlbiAtMTAwMCBhbmQgMTAwMC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiBiZXR3ZWVuIDEgYW5kIDEwIGRlc2NyaWJpbmcgaG93IG1hbnkgcGFpcnMgb2YgbGluZXMmbmJzcDsgYXJlIHJlcHJlc2VudGVkLiZuYnNwOyBUaGUgbmV4dCBOIGxpbmVzIHdpbGwgZWFjaCBjb250YWluIGVpZ2h0IGludGVnZXJzLiZuYnNwOyBUaGVzZSBpbnRlZ2VycyByZXByZXNlbnQgdGhlIGNvb3JkaW5hdGVzIG9mIGZvdXIgcG9pbnRzIG9uIHRoZSBwbGFuZSBpbiB0aGUgb3JkZXIgeDxzdWI+MTxcL3N1Yj4geTxzdWI+MTxcL3N1Yj4geDxzdWI+MjxcL3N1Yj4geTxzdWI+MjxcL3N1Yj4geDxzdWI+MzxcL3N1Yj4geTxzdWI+MzxcL3N1Yj4geDxzdWI+NDxcL3N1Yj4geTxzdWI+NDxcL3N1Yj4uJm5ic3A7IFRodXMgZWFjaCBvZiB0aGVzZSBpbnB1dCBsaW5lcyByZXByZXNlbnRzIHR3byBsaW5lcyBvbiB0aGUgcGxhbmU6IHRoZSBsaW5lIHRocm91Z2ggKHg8c3ViPjE8XC9zdWI+LHk8c3ViPjE8XC9zdWI+KSBhbmQgKHg8c3ViPjI8XC9zdWI+LHk8c3ViPjI8XC9zdWI+KSBhbmQgdGhlIGxpbmUgdGhyb3VnaCAoeDxzdWI+MzxcL3N1Yj4seTxzdWI+MzxcL3N1Yj4pIGFuZCAoeDxzdWI+NDxcL3N1Yj4seTxzdWI+NDxcL3N1Yj4pLiZuYnNwOyBUaGUgcG9pbnQgKHg8c3ViPjE8XC9zdWI+LHk8c3ViPjE8XC9zdWI+KSBpcyBhbHdheXMgZGlzdGluY3QgZnJvbSAoeDxzdWI+MjxcL3N1Yj4seTxzdWI+MjxcL3N1Yj4pLiZuYnNwOyBMaWtld2lzZSB3aXRoICh4PHN1Yj4zPFwvc3ViPix5PHN1Yj4zPFwvc3ViPikgYW5kICh4PHN1Yj40PFwvc3ViPix5PHN1Yj40PFwvc3ViPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlcmUgc2hvdWxkIGJlIE4rMiBsaW5lcyBvZiBvdXRwdXQuJm5ic3A7IFRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBzaG91bGQgcmVhZCBJTlRFUlNFQ1RJTkcgTElORVMgT1VUUFVULiZuYnNwOyBUaGVyZSB3aWxsIHRoZW4gYmUgb25lIGxpbmUgb2Ygb3V0cHV0IGZvciBlYWNoIHBhaXIgb2YgcGxhbmFyIGxpbmVzIHJlcHJlc2VudGVkIGJ5IGEgbGluZSBvZiBpbnB1dCwgZGVzY3JpYmluZyBob3cgdGhlIGxpbmVzIGludGVyc2VjdDogbm9uZSwgbGluZSwgb3IgcG9pbnQuJm5ic3A7IElmIHRoZSBpbnRlcnNlY3Rpb24gaXMgYSBwb2ludCB0aGVuIHlvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IHRoZSB4IGFuZCB5IGNvb3JkaW5hdGVzIG9mIHRoZSBwb2ludCwgY29ycmVjdCB0byB0d28gZGVjaW1hbCBwbGFjZXMuJm5ic3A7IFRoZSBmaW5hbCBsaW5lIG9mIG91dHB1dCBzaG91bGQgcmVhZCAmcXVvdDtFTkQgT0YgT1VUUFVUJnF1b3Q7LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==