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;
 
	double err = 0.000000001;
 
	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;
		deb("round %d\n", i);
		// if (x1 > x2) {
		// 	int tmp = x2;
		// 	x2 = x1;
		// 	x1 = tmp;
		// 	tmp = y2;
		// 	y2 = y1;
		// 	y1 = tmp;
		// }
		// if (y1 > y2) {
		// 	int tmp = y2;
		// 	y2 = y1;
		// 	y1 = tmp;
		// }
		// if (x3 > x4) {
		// 	int tmp = x4;
		// 	x4 = x3;
		// 	x3 = tmp;
		// 	tmp = y4;
		// 	y4 = y3;
		// 	y3 = tmp;
		// }
		// if (y3 > y4) {
		// 	int tmp = y4;
		// 	y4 = y3;
		// 	y3 = tmp;
		// }
		P a = {x1, y1};
		// P b = {x2, y2};
		P c = {x3, y3};
		P d = {x4, y4};
		// P v1 = b - a;
		// P v2 = d - c;
 
		// Same endpoints
		if (a == c or a == d) {
			cout << "YES\n";
			continue;
		}
		// deb("(%d, %d), (%d, %d)\n", x1, y1, x2, y2);
		// deb("(%d, %d), (%d, %d)\n", x3, y3, x4, y4);
		double k = 1.0 * (y2 - y1) / (x2 - x1);
		double k2 = 1.0 * (y4 - y3) / (x4 - x3);
		// deb("%f, %f\n", k, k2);
		if (abs(k - k2) <= err) {
			// deb("tääl\n");
			int l1 = min(x1, x2);
			int l2 = min(x3, x4);
			int r1 = max(x1, x2);
			int r2 = max(x3, x4);
			int l = max(l1, l2);
			int r = min(r1, r2);
			double x = (y3 + k * x1 - y1) / k;
			if (x >= l && x <= r) {
				cout << "YES\n";
				continue;
			}
		}
		// P tmp = a - c;
		double top = (-k * x1) + y1 + (k2 * x3) - y3;
		// deb("-kx1: %f, y1: %d, (k2 * x3): %f, -y3: %d\n", -k * x1, y1, (k2 * x3), -y3);
		double x = top / (k2 - k);
		// deb("top: %f, x: %f\n",top,x);
 
		int l1 = min(x1, x2);
		int l2 = min(x3, x4);
		int r1 = max(x1, x2);
		int r2 = max(x3, x4);
		int l = max(l1, l2);
		int r = min(r1, r2);
		if (x >= l && x <= r) {
			cout << "YES\n";
			continue;
		}
		// Line segments overlap
		// ll cross = (conj(v1)*v2).Y;
		// deb("(%lld, %lld), (%lld, %lld), cross: %lld\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;
 
		// Segments intersect at one point
		// } else {
		// double a, b,
		// if ((x3 < x1 && x4 < x1) || (x3 > x2 && x4 > x2)) {
		// 	cout << "NO\n";
		// 	continue;
		// }
		// 1 1 5 3    6 5 7 1
		// 	double k = 1.0 * (y2 - y1) / (x2 - x1);
		// 	// k2 = 1.0 * (y4 - y3) / (x4 - x3);
		// 	int end = min(x2, x3 - x1);
		// 	int end2 = min(x2, x4 - x1);
		// 	// Either of points c or d is on the line ab
		// 	// if (x1 + k * (x3 - x1) == y3 || x1 + k * (x4 - x1) == y4) {
		// 	// 	cout << "YES\n";
		// 	// 	continue;
		// 	// }
		// 	if (x1 + k * (end) > y3 && x1 + k * (end2) < y4) {
		// 		// deb("eka\n");
		// 		cout << "YES\n";
		// 		continue;
		// 	}
		// 	if (x1 + k * (end) < y3 && x1 + k * (end2) > y4) {
		// 		// deb("toka\n");
		// 		cout << "YES\n";
		// 		continue;
		// 	}
		// }
		cout << "NO\n";
	}
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER