2022CCPC Guilin Site E. Draw a triangle

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;
}