Draw a triangle
题意：
给定两点，求第三个整数点满足三点构成的非退化三角形面积最小
分析：
一开始看成了图论题，以为一直在卡精度（doge
设 \(A(x_1, y_1), B(x_2, y_2), C(x, y)\)，则三角形面积由向量叉积求：\(2S = \vec{AB} × \vec{AC}\)
- \(\vec{AB}\)表示为\((x_2 - x_1, y_2 - y_1)\)，即(a, b);
- \(\vec{AC}\)表示为\((x - x_1, y - y_1)\)，即(X, Y);
此时\(2S = (a, b) × (X, Y) = aY - bX\)
即要求出使得 S 最小的(X, Y)，由扩展欧几里得求解不定二元一次方程组，第一组特解即满足条件
向量的点乘与叉乘
实现：
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int a, b, X1, X2, Y1, Y2;
int x, y;
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve()
{
cin >> X1 >> Y1 >> X2 >> Y2;
a = X2 - X1, b = Y2 - Y1;
exgcd(-b, a, x, y);
x += X1, y += Y1;
cout << x << " " << y << endl;
}
signed main()
{
FAST;
T = 1;
cin >> T;
while (T--)
solve();
return 0;
}