Metszéspont

Azt mondjuk, hogy egy szakasz metsz egy téglalapot, ha van legalább egy közös pontjuk. A téglalaphoz tartozik a négy határoló szakasz és a közöttük lévő terület. Bár a bemenet csak egész számokat tartalmaz, a metszéspontnak nem kell egész koordinátájúnak lennie.

 

Például az alábbi szakasz nem metszi a téglalapot.
A szakasz kezdőpontja: (4,9), végpontja: (11,2)
A téglalap bal felső sarka: (1,5), jobb alsó sarka: (7,1)

 

 

Feladat:

Írj programot, amely megállapítja, hogy az adott szakasz metszi-e az adott téglalapot!

Bemenet:

A bemenet első sora N értéket, a tesztesetek számát tartalmazza. Minden további sor egy-egy tesztesetet foglal magában. A számok a következő sorrendben követik egymást: xstart, ystart, xend, yend, xleft, ytop, xright, ybottom, ahol xstart, ystart a szakasz kezdő, xend, yend a szakasz végpontjai, az xleft, ytop a téglalap bal felső, xright, ybottom pedig a jobb alsó sarka. A számokat szóköz választja el egymástól. A bal felső és a jobb alsó kifejezés nem utal a koordináták sorrendjére.

Kimenet:

A kimeneti állományban tesztesetenként egyetlen sornak kell szerepelnie, benne a T-nek, ha ven metszéspont, illetve az F-nek, ha nincs metszéspont.

Példa:

intersect.in

intersect.ans

1
4
9 11 2 1 5 7 1

F

 

 

(ACM ELTE csapatverseny 2000)