• E. Draw a triangle(计算几何+EXGCD)


    之前学的EXGCD太过于浅显了,很多性质都不是很清楚,正好vp被卡这题了,我们来做一下。

    E. Draw a triangle
    请添加图片描述

    题意:给定两个点的坐标,请你求第三个点的标,保证三个点构成的三角形面积最小。
    数据范围:给定两点的数据范围不超过±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;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
  • 相关阅读:
    使用uniapp框架搭建浙里办微应用(单点登录、埋点、适老化、RPC网关)
    java计算机毕业设计专业招聘网站(附源码、数据库)
    故障定级标准
    QT自制TCP服务器
    【JavaSE】类和对象
    技术分享 | 单元测试体系集成
    农产品溯源中GIS应用
    cobbler实现系统自动化部署与安装
    4.【opencv打开美女热舞视频以及摄像头】
    【花雕动手做】有趣好玩的音乐可视化系列小项目(14)---水杯水瓶灯
  • 原文地址:https://blog.csdn.net/qq_35866893/article/details/127651969