题解：CF407A Triangle

题目传送门

题意

有一个直角三角形的两条直角边长度分别为

a

和

b

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

思路

这题数据很小，考虑一下暴力枚举。时间复杂度为

\Theta(n^3)

，可以通过。我们假设一个点在原点上，然后枚举一条边长为

a

的边且不与坐标轴平行，再得出另一条边。成功则输出 YES 和坐标，没有就直接输出 NO。

code

CPP

#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;
}

题解：CF407A Triangle

文章操作

题目传送门

题意

思路

code

相关推荐

评论

题解：CF407A Triangle