2022CCPC桂林 E. Draw a triangle （gym104008E）

Problem - E - Codeforces

题目大意：在平面坐标系中给出两个整数点的坐标(x1,y1)(x2,y2)，求第三个整数点(x3,y3)使三角形面积最小

-1e9<=x1,x2,y1,y2<=1e9;-1e18<=x3,y3<=1e18

思路：首先画出图：

我们设向量AB=(a,b)向量AC=(x,y)，那么三角形的面积就等于ay-bx的最小值，根据斐蜀定理可知，一个二元一次方程的解c为形如ax+by这样的式子中的a,b的最大公因数的倍数，所以三角形面积的最小值就等于a和-b的最大公因数， 然后我们可以通过扩展欧几里得（扩展欧几里得_Dunyb的博客-CSDN博客）算出向量AC的坐标，然后C的坐标就等于AC的坐标+A的坐标

#include
#include
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll& gcd,ll& x, ll& y)
{//扩展欧几里得
	if (b == 0)
	{
		x = 1, y = 0;
		gcd = a;
	}
	else
	{
		ll g = exgcd(b, a % b, gcd, x, y);
		ll t = y;
		y = x - (a / b) * y;
		x = t;
	}	
	return 0;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		ll x1, y1, x2, y2;
		scanf_s("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
		if (x1 == x2)
		{//如果AB的坐标中有一个是0，则无法用扩展欧几里得，需要特判
			printf("%lld 0\n", x1 + 1);
			continue;
		}
		if (y1 == y2)
		{
			printf("0 %lld\n", y1 + 1);
			continue;
		}
		ll x = x2 - x1, y = y2 - y1;
		ll x3, y3,gcd;
		exgcd(-y, x,gcd, x3, y3);//-x3*y+ye*x=gcd
		printf("%lld %lld\n", x3 + x1, y3 + y1);
	}
	return 0;
}