Line Segment Intersection

#include <bits/stdc++.h>

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");
}

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	// Read the input parameters
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int x1, y1, x2, y2;
		int x3, y3, x4, y4;
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
		P a = {x1, y1};
		P b = {x2, y2};
		P c = {x3, y3};
		P d = {x4, y4};
		P v1 = b - a;
		P v2 = d - c;

		if (a == c or a == d) {
			cout << "YES\n";
			continue;
		}

		// Line segments are on the same line
		// int vx1, vy1, vx2, vy2;
		// vx1 = x2 - x1;
		// vy1 = y2 - y1;
		// vx2 = x4 - x3;
		// vy2 = y4 - y3;
		// int cross = vx1 * vy2 - vx2 * vy1;
		ll cross = (conj(v1)*v2).Y; // 6
		// deb("(%d, %d), (%d, %d), cross: %d\n", v1.X, v1.Y, v2.X, v2.Y, cross);
		if (cross == 0 && ((x3 >= x1 && x3 <= x2) || (x4 >= x1 && x4 <= x2)))
		{
			cout << "YES\n";
			continue;
		} else {
			// double a, b,
			double k;
			k = 1.0 * (y2 - y1) / (x2 - x1);
			// k2 = 1.0 * (y4 - y3) / (x4 - x3);
			if (x1 + k * (x3 - x1) > y3 && x1 + k * (x4 - x1) < y4) {
				// deb("eka\n");
				cout << "YES\n";
				continue;
			}
			if (x1 + k * (x3 - x1) < y3 && x1 + k * (x4 - x1) > y4) {
				// deb("toka\n");
				cout << "YES\n";
				continue;
			}

			// a = 1.0 * y3 - k2 * x3;
			// b = 1.0 * y1 - k * x1;
			// double x = (a - b) / (k - k2);
			// deb("x: %f, a: %f, b: %f, k: %f, k2: %f\n", x, a, b, k, k2);
			// if (x >= x1 && x <= x2 && x >= x3 && x <= x4) {
			// 	cout << "YES\n";
			// 	continue;
			// }
			// int dx1, dy1, dx2, dy2;
			// dx1 = x3 - x1;
			// dy1 = y3 - y1;
			// dx2 = x3 - x2;
			// dy2 = y3 - y2;
			// int d = abs(dx1 * dy2 - dx2 * dy1) / 2;
			// if ((cross > 0 && d <= 0) || (cross < 0 && d >= 0)) {
			// 	cout << "YES\n";
			// 	continue;
			// }
		}
		cout << "NO\n";
	}
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED