Line Segment Intersection

#include <bits/stdc++.h>
#include <cmath>
 
using namespace std;
using ll = long long;
typedef long long C;
typedef complex<C> P;
#define X real()
#define Y imag()
 
// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#define debug_print(fmt, args...) printf(fmt, ##args)
#else
#define deb(fmt, args...)
#define debug_print(fmt, args...)
#endif
 
void print_array(vector<int> in, const string title = "Vector")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		debug_print("%d ", in[i]);
	}
	debug_print("\nDEBUG: ] END\n");
}
 
void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		for (unsigned int j = 0; j < in[i].size(); j++) {
			debug_print("%d ", in[i][j]);
		}
		debug_print("\nDEBUG: ");
	}
	debug_print("DEBUG: ] END\n");
}
 
double angle(int x1, int y1, int x2, int y2) {
	double dot = x1*x2 + y1*y2;
	double cross = x1*y2 - y1*x2;
	return atan2(cross, dot);
}
 
int main(int argc, char *argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	// Read the input parameters
	int n;
	cin >> n;
 
	double err = 0.00001;
 
	for (int i = 0; i < n; i++) {
		ll x1, y1, x2, y2;
		ll x3, y3, x4, y4;
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
		double t1 = (1.0 * (x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4));
		double t2 = (1.0 * (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
		double u1 = -(1.0 * (x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3));
		double u2 = (1.0 * (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
		deb("t1: %f, u1: %f, t2: %f, u2: %f\n", t1, u1, t2, u2);
		if (t1 == 0 && t2 == 0 && u1 == 0 && u2 == 0) {
			deb("tääl\n");
			cout << "YES\n";
			continue;
		}
		double t = t1 / t2;
		double u = u1 / u2;
		deb("t: %f, u: %f\n", t, u);
		if (u >= -err && u <= 1.0 + err && t >= -err && t <= 1.0 + err) {
			cout << "YES\n";
			continue;
		}
		// P a = { x1, y1 };
		// P b = { x2, y2 };
		// P c = { x3, y3 };
		// P d = { x4, y4 };
		// P v1 = b - a;
		// P v2 = d - c;
		// deb("round: %d\n", i);
 
		// Same endpoints
		// if (a == c || a == d || b == c || b == d) {
		// 	cout << "YES\n";
		// 	continue;
		// }
		// C cross = (conj(v1) * v2).Y; // 6
		// deb("(%d, %d), (%d, %d)\n", x1, y1, x2, y2);
		// deb("(%d, %d), (%d, %d)\n", x3, y3, x4, y4);
		// if (cross == 0 &&
		//     ((x3 >= x1 && x3 <= x2) || (x4 >= x1 && x4 <= x2))) {
		// 	cout << "YES\n";
		// 	continue;
		// } else if (cross < 0) {
		// 	// c is above the a-b line
		// 	double ac = angle(x1, y1, x3, y3);
		// 	double ab = angle(x1, y1, x2, y2);
		// 	double ad = angle(x1, y1, x4, y4);
		// 	double bc = angle(x2, y2, x3, y3);
		// 	double ba = angle(x2, y2, x1, y1);
		// 	double bd = angle(x2, y2, x4, y4);
		// 	// if (ac >= ab && ad <= ab && bc )
		// 	P paskaa = d - c;
		// 	C vittu = (conj(c) * paskaa).Y;
		// 	// if vittu < 0 niin vittu on janan alla
		// 	// P m = c - a;
		// 	if (angle(x1, y1, x4, y4) < angle(x1, y1, x2, y2)
		// 			&& -angle(x1, y1, x4, y4) + angle(x1, y1, x3, y3) < M_PI) {
		// 		cout << "YES\n";
		// 		continue;
		// 	}
			// if (angle(x2, y2, ))
			// P q = b - a;
			// deb("%d, %d\n", q.X, q.Y);
			// deb("d - a: %f, b - a: %f\n", angle(0, 0, x4 - x1, y4 - y1), angle(x1, y2, q.X, q.Y));
			// if (arg(d - a) < arg(b - a) && -arg(d - a) + arg(c - a) < M_PI) {
			// 	cout << "YES\n";
			// 	continue;
			// }
			// double dot = m.X * q.X + m.Y * q.Y;
			// C cross2 = (conj(m) * q).Y; // 6
			// double angle = atan2(cross2, dot);
			// deb("angle: %f\n", angle);
			// if (angle <= M_PI) {
			// 	cout << "YES\n";
			// }
			// if (argv(a - c) - argv(b - c) >= M_PI) {
			// 	cout << "YES\n";
			// }
			// if (x3 >= x2) {
			// 	cout << "NO\n";
			// }
			// if (x4 <= x1) {
			// 	cout << "NO\n";
			// }
 
		// } else {
		// 	if (angle(x1, y1, x3, y3) < angle(x1, y1, x2, y2)
		// 			&& -angle(x1, y1, x3, y3) + angle(x1, y1, x4, y4) < M_PI) {
		// 		cout << "YES\n";
		// 		continue;
		// 	}
 
			// if (arg(c - a) < arg(b - a) && -arg(c - a) + arg(d - a) < M_PI) {
			// 	cout << "YES\n";
			// 	continue;
			// }
			// P m = d - a;
			// P q = c - a;
			// double dot = m.X * q.X + m.Y * q.Y;
			// C cross2 = (conj(m) * q).Y; // 6
			// double angle = atan2(cross2, dot);
			// deb("angle: %f\n", angle);
			// if (angle <= M_PI) {
			// 	cout << "YES\n";
			// }
		// }
		cout << "NO\n";
	}
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER