题解：CF407A Triangle

zym20249_ · 2024-12-13 15:18:36 · 题解

题目传送门

题意

有一个直角三角形的两条直角边长度分别为 a 和 b。你的任务是确定是否可以将该三角形定位在平面上，使其任意一条边均不平行于坐标轴，并且所有顶点的坐标为整数。如果存在这样的定位方式，输出对应顶点的坐标。

思路

这题数据很小，考虑一下暴力枚举。时间复杂度为 \Theta(n^3)，可以通过。我们假设一个点在原点上，然后枚举一条边长为 a 的边且不与坐标轴平行，再得出另一条边。成功则输出 YES 和坐标，没有就直接输出 NO。

code

#include<bits/stdc++.h>、、万能头
using namespace std;
int a,b,x,y,i,j,k,g;
int gcd(int x,int y)//不用内部函数，从我做起
{
    if(y==0)return x;
    return gcd(y,x%y);
}
int main()
{
    scanf("%d%d",&a,&b);//时间较少
    for(x=1;x<a;x++)
    {
        y=int(sqrt(a*a-x*x)+0.01);
        if(x*x+y*y==a*a)
        {
            g=gcd(x,y);
            x/=g;
            y/=g;
            k=int(sqrt(b*b/(y*y+x*x))+0.01);
            if(k*k*(x*x+y*y)==b*b)
            {
                if(g*x!=-k*y&&g*y!=k*x)
                {
                    cout<<"YES"<<endl;
                    cout<<"0 0"<<endl;
                    cout<<g*x<<" "<<g*y<<endl;
                    cout<<-k*y<<" "<<k*x<<endl;
                    return 0; 
                }
            }
            x*=g;
        } 
    }
    cout<<"NO"<<endl;
    return 0;
}