Line Segment Intersection

#include <bits/stdc++.h>
 
using namespace std;
 
struct equation_t {
    bool is_vertical;
    float a, b;
};
 
equation_t equation(float x1, float y1, float x2, float y2) {
 
    // y1 = a x1 + b
    // y2 = a x2 + b
 
    // y1 - y2 = a (x1 - x2)
 
    // y1 x2 = a x1 x2 + b x2
    // y2 x1 = a x1 x2 + b x1
 
    // y1 x2 - y2 x1 = b (x2 - x1)
 
    if (x1 == x2) {
        return { true, 0, 0 };
    } else {
        float a = (y1 - y2) / (x1 - x2);
        float b = (y1 * x2 - y2 * x1) / (x2 - x1);
        return {false, a, b};
    }
 
}
 
int main() {
 
    int t;
    cin >> t;
 
    vector<int> inputs(8*t);
    for (int i = 0; i < 8*t; i++)
        cin >> inputs[i];
    
    for (int i = 0; i < t; i++) {
 
        float x1 = (float) inputs[8*i+0], y1 = (float) inputs[8*i+1];
        float x2 = (float) inputs[8*i+2], y2 = (float) inputs[8*i+3];
        float x3 = (float) inputs[8*i+4], y3 = (float) inputs[8*i+5];
        float x4 = (float) inputs[8*i+6], y4 = (float) inputs[8*i+7];
 
        int ix1 = inputs[8*i+0], iy1 = inputs[8*i+1];
        int ix2 = inputs[8*i+2], iy2 = inputs[8*i+3];
        int ix3 = inputs[8*i+4], iy3 = inputs[8*i+5];
        int ix4 = inputs[8*i+6], iy4 = inputs[8*i+7];
 
        equation_t l12 = equation(x1, y1, x2, y2);
        equation_t l34 = equation(x3, y3, x4, y4);
 
        if (l12.is_vertical && l34.is_vertical) {
 
            if (ix1 == ix3 && ((iy1 >= min(iy3, iy4) && iy1 <= max(iy3, iy4)) || (iy2 >= min(iy3, iy4) && iy2 <= max(iy3, iy4)))) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
 
        } else if (l12.is_vertical) {
 
            float x = x1;
            float y = l34.a * x + l34.b;
 
            int iy = (int) round(y), ix = (int) round(x);
 
            if (iy >= min(iy1, iy2) && iy <= max(iy1, iy2) && ix >= min(ix3, ix4) && ix <= max(ix3, ix4)) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
 
        } else if (l34.is_vertical) {
 
            float x = x3;
            float y = l12.a * x + l12.b;
 
            int iy = (int) round(y), ix = (int) round(x);
 
            if (iy >= min(iy3, iy4) && iy <= max(iy3, iy4) && ix >= min(ix1, ix2) && ix <= max(ix1, ix2)) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
 
        } else {
 
            // y = a1 x + b1
            // y = a2 x + b2
 
            // a1 x + b1 = a2 x + b2
            // x (a1 - a2) = (b2 - b1)
 
            float epsilon = 10e-9;
 
            if (abs(l12.a - l34.a) <= epsilon) {
 
                // y = ax + b1
                // y = ax + b2
 
                if (abs(l12.b - l34.b) <= epsilon) {
                    
                    if ((ix1 >= min(ix3, ix4) && ix1 <= max(ix3, ix4)) || (ix2 >= min(ix3, ix4) && ix2 <= max(ix3, ix4))) {
                        cout << "YES" << endl;
                    } else {
                        cout << "NO" << endl;
                    }
 
                } else {
                    cout << "NO" << endl;
                }
 
            } else {
 
                float x = (l34.b - l12.b) / (l12.a - l34.a);
                float y = l12.a * x + l12.b;
 
                float ix = (int) round(x), iy = (int) round(y);
 
                if (iy >= min(iy1, iy2) && iy <= max(iy1, iy2) && iy >= min(iy3, iy4) && iy <= max(iy3, iy4) &&
                    ix >= min(ix1, ix2) && ix <= max(ix1, ix2) && ix >= min(ix3, ix4) && ix <= max(ix3, ix4)) {
                    cout << "YES" << endl;
                } else {
                    cout << "NO" << endl;
                }
 
            }
 
 
        }
 
    }
 
}

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: ACCEPTED