当前位置: 首页> 汽车> 报价 > 哈尔滨企业网站建站推荐_厦门建网站多少钱_上海网站seo_国际重大新闻事件2023

哈尔滨企业网站建站推荐_厦门建网站多少钱_上海网站seo_国际重大新闻事件2023

时间:2025/7/10 13:02:28来源:https://blog.csdn.net/2301_81224780/article/details/142768621 浏览次数: 0次
哈尔滨企业网站建站推荐_厦门建网站多少钱_上海网站seo_国际重大新闻事件2023

Problem - E - Codeforces

题意:给定两个点的坐标求第三个点并且使得三个点围成的三角形面积最小;

这道题涉及了很多知识点:

1.在二维空间中,两个向量a,b叉乘,|a*b|在数值上等于以向量a和向量b为邻边构成的平行四边形的面积;

数量积(点积):意义为A在B上的投影和B的长度的乘积。

AB=x1x2+y1y2

向量积(叉积):绝对值为向量A和B所围的四边形的面积,可以变相的算三角形面积

A*B=x1 * y2 - x2 * y1

所以这道题三角形的面积可以这么做,只是最后的面积*0.5;

我们已知A,B两点,就可以只带AB向量(xb-xa,ya-yb);设常量a,b;

如果设AC的坐标是(x,y)则最后的c的坐标就是(x+xa,y+ya);

AB(x2-x1,y2-y1);(a,b)

AC(x3-x1,y3-y1); (x,y)

所以我们就需要AB×AC就是(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) ;

                                                  (a   *   y)     -(   x  *    b )

就是S=0.5*(ax-b*y)

用拓展欧几里得算法求解二元一次方程组的最小值

由裴蜀定理可知a*x-b*y=gcd(a,b)的倍数;

最小就是a*x+b*y=gcd(a,b);

所以a*x-b*y的最小值就是gcd(a,-b)的最大公因数

所以我们用扩展欧几里得就能求出x,y;

C的坐标只用在此基础上加上a的坐标即可

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;//当a是b的倍数时,a*x+b*y=a;//余数b等于0,除数a就是最大公约数return a;//返回最大公约数}else{int k=exgcd(b,a%b,x,y);//此时的x1和y1是上一层的状态所以方程就为//b*x1+(a%b)*y1=gcd(a,b);//->b*x1+(a-(a/b)*b)*y1=gcd(a,b);//->a*y1+b*(x1-(a/b)*y1)=gcd(a,b);int t=y;y=x-(a/b)*y;//求余数x=t;return k;}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;while(t--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;int a=(x2-x1);int b=(y1-y2);if(x1==x2){cout<<x1+1<<" "<<y1<<endl;}else if(y2==y1){cout<<x1<<" "<<y2+1<<endl;}else{int x,y;int _gcd=exgcd(b,a,x,y);cout<<x+x1<<" "<<y+y1<<endl;}}
}

关键字:哈尔滨企业网站建站推荐_厦门建网站多少钱_上海网站seo_国际重大新闻事件2023

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: