之前学的EXGCD太过于浅显了,很多性质都不是很清楚,正好vp被卡这题了,我们来做一下。
题意:给定两个点的坐标,请你求第三个点的标,保证三个点构成的三角形面积最小。
数据范围:给定两点的数据范围不超过±1e9,第三点表示范围不超过±1e18
知识点1:三角形面积公式
我们都知道,最常用的一个公式是海伦公式,但是其缺点也很明显,算距离,开方等等,所以在如此大的数据面前很容易就会崩盘,而且事实证明,这题在这种思路下也没有可解的余地。
已知三角形三个点的坐标,则其表示的三角形面积可以表示为
(x2 - x1) * (y3 - y1) - (y2 - y1)*(x3 - x1)
推导过程
首先我们需要知道平面向量的两个计算:数量积和向量积
以下均默认向量A(x1,y1),向量B(x2,y2)
数量积(点积):意义为A在B上的投影和B的长度的乘积。
AB=x1x2+y1y2
向量积(叉积):绝对值为向量A和B所围的四边形的面积,可以变相的算三角形面积
A*B=x1 * y2 - x2 * y1
所以根据叉积公式,我们可以算出三条边中任意两条边的向量形式,然后根据这两个向量来算出三角形面积公式为
S=0.5*(x2 - x1) * (y3 - y1) - (y2 - y1)*(x3 - x1)
我们知道两个点的坐标,x1 y1 x2 y2,现在设第三个点的坐标为x3 y3
根据上述叉积公式有如下等式
S=0.5*(x2 - x1) * (y3 - y1) - (y2 - y1)*(x3 - x1)
这个等式里X3,Y3均为未知量,所以不妨将含有未知量的项设为x和y,即(y3 - y1)为y, (x3 - x1)为x
已知量(x2 - x1)设为a, - (y2 - y1)设为b
则有如下二元一次不定方程
S=0.5(ax+by)
忽略0.5,可以设为其在求解二元一次不定方程组的一组解,使得S取得最小值
我们知道exgcd可以求解不定二元一次方程组问题,那么这里来说一下注意事项
1.我们无法求解当系数a,b为负数的情况,所以当a和b系数为负时,需要对x和y取相反数进行等价的代还。
2.求出的第一组特解可以使得等式右侧最小
二元一次不定方程 (exgcd)
具体的更多问题还是建议去这里看一下。
#include
using namespace std;
#define int long long
void exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return ;
}
exgcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-a/b*y;
}
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int ti;
for(cin>>ti;ti;ti--)
{
int x1,y1,x2,y2,x3,y3;
cin>>x1>>y1>>x2>>y2;
///2*S=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)
///gcd(a,b)=a*x+b*y
int a=-(y2-y1),b=x2-x1;
int fx=1,fy=1;
if(a<0)
{
fx=-1;
a*=fx;
}
if(b<0)
{
fy=-1;
b*=fy;
}
exgcd(a,b,x3,y3);
x3*=fx;
y3*=fy;
x3+=x1;
y3+=y1;
cout<<x3<<" "<<y3<<'\n';
}
return 0;
}