E - Draw a triangle
前言
$exgcd$ 和裴蜀定理好像还挺常用的,之前也写过另外一个题的题解:
D. Not Quite Lee(纯数学,非常棒的抽丝剥茧的推理)
题意
给定点 $(x_1, y_1)$ 和点 $(x_2, y_2)$,求第三个点 $(x_3,y_3)$,使得三点构成的三角形面积最小,但是面积不可以是 $0$。
做法
设三点为 $A,B,C$,然后用向量求三角形面积,会得到:
$|\,AB * BC\,|\,/\,2$
如果用向量 $(a,b)$代表 $AB$,用向量 $(x,y)$ 代表 $AC$,那么上面的式子就是$|\,ay - bx\,|\,/\,2 $。
根据裴蜀定理,这个方程有解,当且仅当面积 $S$ 是$gcd(a,b)$ 的倍数。
显然面积最小值就是 $gcd(a,b)$ 了。
剩下的事情,就是用 $exgcd$ 求出一组 $(x, y)$,最后再算出 $(x_3,y_3)$ 即可。
注意特判 $AB$ 平行坐标轴的情况。
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x;
x = y;
y = z - y * (a / b);
return d;
}
void solve()
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int a = x1 - x2;
int b = y1 - y2;
if(a == 0){
cout << x1 + 1 << " " << y1 << "\n";
return;
}
if(b == 0){
cout << x1 << " " << y1 + 1 << "\n";
return;
}
int x, y;
int d = exgcd(-b, a, x, y);
// cout << a << " " << b << " " << d << "\n";
// cout << a * x - b * y << "\n";
x += x2;
y += y2;
cout << x << " " << y << "\n";
}