Shamos-Hoye

/*
Working shamos-hoey algorithm in c++ - finds if any two line segments in set of segments intersects
input:
t - test cases,
in each test case n - number of lines
in n lines:
start, end, a, b:
start - x-cord of left endpoint
end - xcord of right endpoint
a, b are factors of line equation
y = a*x + b

prints TAK if intersection exists, NIE if not
*/
#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll globalX;

struct point {
	ll x;
	ll y;
	bool left; //czy lewy
	int n; //do której lini należy
	point() {}
	point(const ll &x, const ll &y, bool l, const int &i) {
		this->x = x; this->y = y; left = l; n = i;
	}
	bool operator <(const point &p) const {
		return this->x < p.x;
		return this->y < p.y;
	}
};

struct segment {
	point A, B;
	ll a, b;
	segment() {}
	segment(const point &P, const point &K) {
		A = P; B = K;
		B.x - A.x == 0 ? a = 0 : a = (B.y - A.y) / (B.x - A.x);
		b = A.y - a*A.x;
	}
	bool operator <(const segment &s) const {
		return a*globalX + b < s.a*globalX + s.b;
	}
};

ll product(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
	return (((x2 - x1)*(y3 - y1)) - ((x3 - x1)*(y2 - y1)));
}

bool between(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) { //dla pokrywających się
	if (
		(min(x1, x2) <= x3) && (x3 <= max(x1, x2)) &&
		(min(y1, y2) <= y3) && (y3 <= max(y1, y2))
		) return true;
	return false;
}

bool crossover(const segment &a, const segment &b) {
	ll p1 = product(a.A.x, a.A.y, b.A.x, b.A.y, a.B.x, a.B.y);
	ll p2 = product(a.A.x, a.A.y, b.B.x, b.B.y, a.B.x, a.B.y);
	ll p3 = product(b.A.x, b.A.y, a.A.x, a.A.y, b.B.x, b.B.y);
	ll p4 = product(b.A.x, b.A.y, a.B.x, a.B.y, b.B.x, b.B.y);

	if (((p1 > 0 && p2 < 0) || (p1 < 0 && p2 > 0))
		&&
		((p3 < 0 && p4 > 0) || (p3 > 0 && p4 < 0))) return true;
	else if (p1 == 0 && between(a.A.x, a.A.y, a.B.x, a.B.y, b.A.x, b.A.y)) return true;
	else if (p2 == 0 && between(a.A.x, a.A.y, a.B.x, a.B.y, b.B.x, b.B.y)) return true;
	else if (p3 == 0 && between(b.A.x, b.A.y, b.B.x, b.B.y, a.A.x, a.A.y)) return true;
	else if (p4 == 0 && between(b.A.x, b.A.y, b.B.x, b.B.y, a.B.x, a.B.y)) return true;
	else return false;
}

bool f() {
	int n;
	scanf("%d", &n);
	vector<segment> S;
	S.resize(n);
	vector<point> points;
	points.resize(2 * n);

	ll start, end;
	ll a, b;
	for (int i = 0; i < n; i++) {
		scanf("%lld %lld %lld %lld", &start, &end, &a, &b);
		points[2 * i] = point(start, start*a + b, true, i);
		points[2 * i + 1] = point(end, end*a + b, false, i);
		S[i] = segment(points[2 * i], points[2 * i + 1]);
	}

	sort(points.begin(), points.end());
	multiset<segment> BST;

	for (int i = 0; i < 2 * n; i++) {
		globalX = points[i].x;
		if (points[i].left) {
			multiset<segment>::iterator it = BST.insert(segment(S[points[i].n].A, S[points[i].n].B));
			multiset<segment>::iterator above;
			multiset<segment>::iterator below;
			if (it != BST.begin()) {
				below = (--it)++;
				if (crossover(*it, *below)) return true;
			}
			if (++it != BST.end()) {
				above = it--;
				if (crossover(*it, *above)) return true;
			}
		}
		else {
			segment a = segment(S[points[i].n].A, S[points[i].n].B);
			multiset<segment>::iterator it = BST.find(a);
			if (it != BST.begin() && ++it != BST.end()) {
				multiset<segment>::iterator above = it;
				multiset<segment>::iterator below = --(--it);
				if (crossover(*above, *below)) return true;
				BST.erase(*(++it));
			}
		}
	}
	return false;
}

int main() {
	int z;
	scanf("%d", &z);
	while (z--) {
		if (f()) printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}
/*
2
3
0 5 1 0
5 10 -1 5
10 15 0 0

4
0 5 0 0
0 5 0 1
0 3 -1 3
0 3 1 -1

> NIE
> TAK
=== OK
1
3
0 6 -1 5
3 5 -1 7
4 5 -5 26

> TAK
=== OK
1
3
0 5 1 0
5 10 -1 10
10 15 0 0

> TAK
=== OK
1
5
0 10 1 0
1 10 1 1
2 10 1 2
3 10 1 3
4 10 1 5

> NIE
== OK
*/