UVa378_homo-coordinates.cpp

#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> void max_self(T & a, const T & b) { if(a < b) a = b; }
template<class T> void min_self(T & a, const T & b) { if(a > b) a = b; }
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);

class line{
public:
    double a, b, c;
};

int main(){
    FAST_IO
     
    int T; cin >> T;
    line X, Y, l1, l2, pt;
    X.c = 1, Y.c = 1;

    auto cross = [&](line &r, line &o, line &t){
        r.a = o.b * t.c - t.b * o.c;
        r.b = t.a * o.c - o.a * t.c;
        r.c = o.a * t.b - o.b * t.a; 
        return;
    };

    cout << "INTERSECTING LINES OUTPUT\n";
    while(T--){
        cin >> X.a >> X.b >> Y.a >> Y.b;
        cross(l1, X, Y);
     
        cin >> X.a >> X.b >> Y.a >> Y.b;
        cross(l2, X, Y);
     
        cross(pt, l1, l2);
     
        if(pt.c){
            cout << "POINT ";
            PRECISION(2);
            cout << pt.a / pt.c << " " << pt.b / pt.c << "\n";
        }else if(pt.a || pt.b){
            cout << "NONE\n";
        }else{
            cout << "LINE\n";
        }
     
    }
    cout << "END OF OUTPUT\n";
}

Here is the answer: The meet of two lines and the join of two points are both handled by the cross product in a projective setting. Let’s work it out. We use capital letters (X,Y,Z) for coordinates in 3 space and small letters (x,y) for our 2D Cartesian plane, which we elevate to Z=1. A line through the origin and point (X,Y,Z) in 3 space has parametric representation t(X,Y,Z). Only the ratio of the coordinates matter, so let’s abbreviate this line (X:Y:Z). It intersects our Cartesian plane, the Z=1 plane, at (XZ,YZ), i.e. x=XZ,y=YZ So (X:Y:Z) is a projective way to refer to a point in the Cartesian plane, namely the point (X/Z,Y/Z). The Cartesian point (a,b) corresponds to the line in three space through the origin (a : b : 1). What about the Cartesian line ax+by+c=0? When we include the origin in three space, we get a plane whose equation is aX+bY+cZ=0. We abbreviate the plane and its corresponding line in the Cartesian plane as [a : b : c] as the values only matter in ratio. The join of two points (a : b : c) and (d : e : f), i.e the line between two points, which we’ll write as the product (a : b : c)(d : e : f), is given by the cross product. (a : b : c)(d : e : f)=[bf−ce : cd−af : ae−bd] The meet of two lines [a : b : c] and [d : e : f] is given identically by the cross product: [a : b : c][d : e : f]=(bf−ce : cd−af : ae−bd) Let’s work out an example where we know the answer. Line one points (0,0),(1,1), line two points (1,3),(3,1) so a final answer of (2,2). The line between (0,0) and (1,1) is (0:0:1)(1:1:1)=[0(1)−1(1):1(1)−0(1):0(1)−0(1)]=[−1:1:0] which is −x+y+0=0, aka y=x✓ The line between (1,3) and (3,1) is (1:3:1)(3:1:1)=[3(1)−1(1):1(3)−1(1):1(1)−3(3)] =[2:2:−8]=[1:1:−4] which is x+y+−4=0, aka x+y=4✓ The meet we seek is ((0:0:1)(1:1:1))((1:3:1)(3:1:1)) =[−1:1:0][1:1:−4]=(1(−4)−0(1):0(1)−(−1)(−4):−1(1)−1(1)) =(−4:−4:−2)=(2:2:1)=(2,2)✓ Math works!