#include<bits/stdc++.h> #define ll long long // input: 2 points // output: (a, b, c) represents the equation: ax + by = c template <typename T> vector<T> line_passing_2_points(T x1, T y1, T x2, T y2) { T a = y2 - y1; T b = x1 - x2; T c = a*(x1) + b*(y1); T gcd; gcd = __gcd(a, b); gcd = __gcd(gcd, c); a/= gcd; b/= gcd; c/= gcd; if (a < 0) { a = -a; b = -b; c = -c; } vector<T> line = {a, b, c}; return line; }