UVa 191 - Intersection

// UVa 191 - Intersection

#include <stdio.h>

struct point {
	double x, y;
};

struct line {
	double a, b, c;
};

line points_to_line(point p, point q) {
	line l;
	l.a = p.y - q.y;
	l.b = q.x - p.x;
	l.c = -l.a * p.x - l.b * p.y;
	return l;
}

bool are_parallel(line l1, line l2) {
	return l1.b * l2.a == l2.b * l1.a;
}

bool are_same(line l1, line l2) {
	if ((l1.b == 0) ^ (l2.b == 0))
		return false;
	else if (l1.b == 0 && l2.b == 0)
		return l1.c / l1.a == l2.c / l2.a;
	else
		return l1.a / l1.b == l2.a / l2.b && l1.c / l1.a == l2.c / l2.a;
}

point intersection(line l1, line l2) {
	point p;
	p.y = (l2.c * l1.a - l1.c * l2.a) / (l1.b * l2.a - l2.b * l1.a);
	p.x = (l2.c * l1.b - l1.c * l2.b) / (l1.a * l2.b - l2.a * l1.b);
	return p;
}

void swp(int& a, int&b) {
	int c = a;
	a = b;
	b = c;
}

#define order(a,b) if (a>b) swp(a,b)

int main() {
	int t;
	for (scanf("%d", &t); t; t--) {

		int xstart, ystart, xend, yend, xleft, ytop, xright, ybottom;
		scanf("%d%d%d%d%d%d%d%d", &xstart, &ystart, &xend, &yend, &xleft, &ytop,
				&xright, &ybottom);

		order(xleft, xright);
		order(ybottom, ytop);
		bool sol = xleft <= xstart && xstart <= xright && ybottom <= ystart
				&& ystart <= ytop;

		if (!sol) {

			line l = points_to_line( { xstart, ystart }, { xend, yend });
			order(xstart, xend);
			order(ystart, yend);

			line r[4];
			r[0] = points_to_line( { xleft, ytop }, { xleft, ybottom });
			r[1] = points_to_line( { xleft, ytop }, { xright, ytop });
			r[2] = points_to_line( { xright, ybottom }, { xright, ytop });
			r[3] = points_to_line( { xright, ybottom }, { xleft, ybottom });

			for (int i = 0; i < 4; i++)
				if (!are_parallel(r[i], l) && !are_same(r[i], l)) {
					point p = intersection(r[i], l);
					if (xstart <= p.x && p.x <= xend && ystart <= p.y
							&& p.y <= yend && xleft <= p.x && p.x <= xright
							&& ybottom <= p.y && p.y <= ytop) {
						sol = true;
						//printf("D: i=%d p=%.2f,%.2f\n", i, p.x, p.y);
						break;
					}
				}
		}

		if (sol)
			printf("T\n");
		else
			printf("F\n");
	}

	return 0;
}