시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB369587268723.862%

문제

입력으로 주어진 선분과 직사각형이 교차하는지 아닌지를 구하는 프로그램을 작성하시오.

위의 그림에서 선분의 시작점은 (4,9), 끝점은 (11,2) 이며, 직사각형의 왼쪽 위 좌표는 (1,5), 오른쪽 아래 좌표는 (7, 1)이다. 또, 선분과 직사각형은 교차하지 않는다.

선분과 직사각형이 교차하려면 적어도 한 점을 공유해야한다. 입력으로 주어지는 좌표는 모두 절댓값이 50보다 작거나 같은 정수이지만, 교점은 정수 좌표가 아닐 수도 있다. 직사각형의 넓이는 0일 수도 있다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, xstart ystart xend yend xleft ytop xright ybottom로 이루어져 있다. (xstart, ystart)는 선분의 시작점, (xend, yend)는 선분의 끝점이고, (xleft, ytop)는 직사각형의 한 쪽 모서리 좌표, (xright, ybottom)는 직사각형 반대쪽 모서리 좌표이다.

xleft ytop xright ybottom 은 직사각형의 왼쪽, 오른쪽, 위, 아래 좌표를 의미하는 것은 아니며, 변수명은 우연의 일치이다.

출력

각 테스트 케이스마다 선분과 직사각형이 교차하면 'T'를, 교차하지 않으면 'F'를 한 줄에 하나씩 출력한다. 선분의 두 점이 사각형 내부에 있을 때도 'T'이다.

예제 입력 1

1
4 9 11 2 1 5 7 1

예제 출력 1

F
W3sicHJvYmxlbV9pZCI6IjY0MzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNTBcdWNjMjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMTIwXHViZDg0XHVhY2ZjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9JbnRlcnNlY3Rpb24uZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTkwcHg7IHdpZHRoOjIxN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc0MCAoNCw5KSwgXHViMDVkXHVjODEwXHVjNzQwICgxMSwyKSBcdWM3NzRcdWJhNzAsIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoMSw1KSwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWM4OGNcdWQ0NWNcdWIyOTQgKDcsIDEpXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YzEyMFx1YmQ4NFx1YWNmYyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHViZDg0XHVhY2ZjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWFkNTBcdWNjMjhcdWQ1NThcdWI4MjRcdWJhNzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWM4MTBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWJhYThcdWI0NTAgXHVjODA4XHViMzEzXHVhYzEyXHVjNzc0IDUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHVjOWMwXHViOWNjLCBcdWFkNTBcdWM4MTBcdWM3NDAgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM1NDRcdWIyZDAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjExM1x1Yzc3NFx1YjI5NCAwXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCB4PHN1Yj5zdGFydDxcL3N1Yj4geTxzdWI+c3RhcnQ8XC9zdWI+IHg8c3ViPmVuZDxcL3N1Yj4geTxzdWI+ZW5kPFwvc3ViPiB4PHN1Yj5sZWZ0PFwvc3ViPiB5PHN1Yj50b3A8XC9zdWI+IHg8c3ViPnJpZ2h0PFwvc3ViPiB5PHN1Yj5ib3R0b208XC9zdWI+XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICh4PHN1Yj5zdGFydDxcL3N1Yj4sIHk8c3ViPnN0YXJ0PFwvc3ViPilcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzgxMCwgKHg8c3ViPmVuZDxcL3N1Yj4sIHk8c3ViPmVuZDxcL3N1Yj4pXHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWIwNWRcdWM4MTBcdWM3NzRcdWFjZTAsICh4PHN1Yj5sZWZ0PFwvc3ViPiwgeTxzdWI+dG9wPFwvc3ViPilcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDU1YyBcdWNhYmQgXHViYWE4XHVjMTFjXHViOWFjIFx1Yzg4Y1x1ZDQ1YywgKHg8c3ViPnJpZ2h0PFwvc3ViPiwgeTxzdWI+Ym90dG9tPFwvc3ViPilcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmMxOFx1YjMwMFx1Y2FiZCBcdWJhYThcdWMxMWNcdWI5YWMgXHVjODhjXHVkNDVjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD54PHN1Yj5sZWZ0PFwvc3ViPiB5PHN1Yj50b3A8XC9zdWI+IHg8c3ViPnJpZ2h0PFwvc3ViPiB5PHN1Yj5ib3R0b208XC9zdWI+IFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzcwNCwgXHVjNTQ0XHViNzk4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzU0NFx1YjJjOFx1YmE3MCwgXHViY2MwXHVjMjE4XHViYTg1XHVjNzQwIFx1YzZiMFx1YzVmMFx1Yzc1OCBcdWM3N2NcdWNlNThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjMTIwXHViZDg0XHVhY2ZjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWFkNTBcdWNjMjhcdWQ1NThcdWJhNzQgJiMzOTtUJiMzOTtcdWI5N2MsIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgJiMzOTtGJiMzOTtcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWMxMjBcdWJkODRcdWM3NTggXHViNDUwIFx1YzgxMFx1Yzc3NCBcdWMwYWNcdWFjMDFcdWQ2MTUgXHViMGI0XHViZDgwXHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWIzYzQgJiMzOTtUJiMzOTtcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNjQzOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkludGVyc2VjdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBoYXMgdG8gZGVjaWRlIHdoZXRoZXIgYSBnaXZlbiBsaW5lIHNlZ21lbnQgaW50ZXJzZWN0cyBhIGdpdmVuIHJlY3RhbmdsZS48XC9wPlxyXG5cclxuPHA+QW4gZXhhbXBsZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5saW5lOiBzdGFydCBwb2ludDogKDQsOSk8XC9saT5cclxuXHQ8bGk+ZW5kIHBvaW50OiAoMTEsMik8XC9saT5cclxuXHQ8bGk+cmVjdGFuZ2xlOiBsZWZ0LXRvcDogKDEsNSk8XC9saT5cclxuXHQ8bGk+cmlnaHQtYm90dG9tOiAoNywxKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL0ludGVyc2VjdGlvbi5naWZcIiBzdHlsZT1cImhlaWdodDoxOTBweDsgbGluZS1oZWlnaHQ6MjAuNzk5OTk5MjM3MDYwNXB4OyB3aWR0aDoyMTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTogTGluZSBzZWdtZW50IGRvZXMgbm90IGludGVyc2VjdCByZWN0YW5nbGU8XC9wPlxyXG5cclxuPHA+VGhlIGxpbmUgaXMgc2FpZCB0byBpbnRlcnNlY3QgdGhlIHJlY3RhbmdsZSBpZiB0aGUgbGluZSBhbmQgdGhlIHJlY3RhbmdsZSBoYXZlIGF0IGxlYXN0IG9uZSBwb2ludCBpbiBjb21tb24uIFRoZSByZWN0YW5nbGUgY29uc2lzdHMgb2YgZm91ciBzdHJhaWdodCBsaW5lcyBhbmQgdGhlIGFyZWEgaW4gYmV0d2Vlbi4gQWx0aG91Z2ggYWxsIGlucHV0IHZhbHVlcyBhcmUgaW50ZWdlciBudW1iZXJzLCB2YWxpZCBpbnRlcnNlY3Rpb24gcG9pbnRzIGRvIG5vdCBoYXZlIHRvIGxheSBvbiB0aGUgaW50ZWdlciBncmlkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG4gdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgdGhlIG51bWJlciBuLiBFYWNoIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIG9uZSB0ZXN0IGNhc2Ugb2YgdGhlIGZvcm1hdDogeHN0YXJ0IHlzdGFydCB4ZW5kIHllbmQgeGxlZnQgeXRvcCB4cmlnaHQgeWJvdHRvbSB3aGVyZSAoeHN0YXJ0LCB5c3RhcnQpIGlzIHRoZSBzdGFydCBhbmQgKHhlbmQsIHllbmQpIHRoZSBlbmQgcG9pbnQgb2YgdGhlIGxpbmUgYW5kICh4bGVmdCwgeXRvcCkgdGhlIHRvcCBsZWZ0IGFuZCAoeHJpZ2h0LCB5Ym90dG9tKSB0aGUgYm90dG9tIHJpZ2h0IGNvcm5lciBvZiB0aGUgcmVjdGFuZ2xlLiBUaGUgZWlnaHQgbnVtYmVycyBhcmUgc2VwYXJhdGVkIGJ5IGEgYmxhbmsuIFRoZSB0ZXJtcyB0b3AgbGVmdCBhbmQgYm90dG9tIHJpZ2h0IGRvIG5vdCBpbXBseSBhbnkgb3JkZXJpbmcgb2YgY29vcmRpbmF0ZXMuPFwvcD5cclxuXHJcbiIsIm91dHB1dCI6IiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 1995 A번