CodeForces/407A

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Triangle	★☆☆☆☆	答案正确	100	2015-02-24 15:46:16	没看清题目（0）

• 来自寒假练习：2015 Winter Day 1 div2 E题
• 原题链接：http://codeforces.com/problemset/problem/407/A

题意

给出两条边长a,b，问能否用这两条边构造直角三角形，三个顶点坐标值都为整数，且三条边不和坐标轴平行。

题解

• 由题意不如把一个点放在原点，两条边分别在第一、第二象限。
• 枚举i≤a，记录满足以下条件的i，我们知道向量(,)即为满足题意的一组边：

1. i是完全平方数（存在整数使得）；
2. 也是完全平方数；

• 类似的枚举符合条件j≤b并记录(-,)。
• 之后再枚举(i,j)，筛选出能构成直角三角形、且y分量不相同的一对向量，输出即可。

好吧，第一次交的时候没看见是直角三角形……

代码

407A.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<iostream> #include<string> #include<vector> #include<algorithm> #include<cstring> #include<cmath> #include<set> #define sqr(x) ((x)*(x)) #define dsi(n) int n;scanf("%d",&n) #define si(n) scanf("%d",&n) #define f(i,n) for(int i=1;i<=n;++i) #define fi(n) f(i,n) #define f0(i,n) for(int i=0;i!=n;++i) #define fd(i,n) for(int i=n;i>=1;--i) #define ci const int& #define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i) std::set< std::pair<int,int> > t,p; int getl(std::pair<int,int> a) { return a.first*a.first+a.second*a.second; } bool isRight(std::pair<int,int> a,std::pair<int,int> b) { std::pair<int,int> c=std::make_pair(a.first+b.first,a.second-b.second); int la=getl(a),lb=getl(b),lc=getl(c); return la+lb==lc||la+lc==lb||lb+lc==la; } int main() { dsi(a);dsi(b); fi(a*a-1) if(sqr(round(sqrt(i)))==i&&sqr(round(sqrt(a*a-i)))==a*a-i) t.insert(std::make_pair(round(sqrt(i)),round(sqrt(a*a-i)))); fi(b*b-1) if(sqr(round(sqrt(i)))==i&&sqr(round(sqrt(b*b-i)))==b*b-i) p.insert(std::make_pair(round(sqrt(i)),round(sqrt(b*b-i)))); //std::cout<<t.size(); foreach(i,t) { foreach(j,p) { if(i->second!=j->second&&isRight(*i,*j)) { std::cout<<"YES\n"<<"0 0\n"<<i->first<<" "<<i->second<<"\n"<<-j->first<<" "<<j->second; return 0; } } } std::cout<<"NO"; return 0; }