2017年8月12日提高组T3 YMW的三角形

Description

YMW终于思考完数学题了，因为数学给人力量，所以他现在浑身都充满了力量。然而lyy俯视YMW，不屑地说道，你小学数学题都不会做，还在这嚣张？你看我们的电脑屏幕，可以是一个二维直角坐标系，你把手上那把三角板放在屏幕上，现在你告诉我它的每个顶点能否都在整数点上吗？（整数点：一个点，它的x和y坐标都为整数）

Input

多组数据，每组数据三个数表示三角形的三条边
输入以文件结束结尾

Output

对于每组数据，如果可以则输出Yes，不可以则输出No

Hint

数据范围：
数据组数不超过10组，不少于5组
对于30%的数据，三边长均小于1 000
对于70%的数据，三边长均小于100 000
对于100%的数据，三边长均小于10 000 000

Source

BY BPM

Solution

绿色就是力量！

又是一题被大小写耽误的。。

如图，已知任意一个在平面直角坐标系中的三角形都可以被矩形套住。那么我们可以固定一个点不动，通过枚举图中的边x的长得到h并判断是否是整数。

同理，我们可以通过海伦公式求面积，求a边上的高ha。那么通过ha/b可以确定夹角的大小，x/a同理。那么剩下的三角形就出来了，判断剩下的点是否是整点即可

但是，这样会面临卡精度的问题，例如92295 6688 92537这组数据，于是我可耻地看了一波标

我们可以通过平移旋转的方式改变三角形的位置，那么我们固定三角形在原点，可以发现旋转相当于以原点为圆心作半径为a的$1/4$圆，以原点为圆心作半径为b的1/2圆。

已知在半径为r的圆上点都满足$x^2+y^2=r^2$，通过枚举x坐标我们可以找出所有的整点，枚举判断是否存在两点距离为c即可。根据某项定理可得这样的整点不会超过$\sqrt{n}$个，这样就是O(n)的了。

根据对称性我们只用找a/2次，b/2次，a、b为最短两边

Code

#include <stdio.h>
#include <math.h>
#include <vector>
#define rep(i, st, ed) for (ll i = st; i <= ed; i += 1)
#define EPS 1e-6
#define ll long long
#define db double
struct pos{ll x, y;}va[10001],vb[10001];
inline void swap(ll &a, ll &b){a^=b;b^=a;a^=b;}
inline bool teg(db x){return fabs(x - floor(x)) <= EPS;}
int main(void){int ra, rb, rc;while (~scanf("%d %d %d", &ra, &rb, &rc)){ll a = ra, b = rb, c = rc;if (b < a && b < c){swap(a, b);}if (c < a && c < b){swap(a, c);}if (c < b){swap(b, c);}int cntA = 0, cntB = 0;rep(x, 0, a / 2){db y = sqrt(a*a*1.0-x*x*1.0);if (fabs(y-(int)y)<=EPS){va[++ cntA] = (pos){x, y};va[++ cntA] = (pos){y, x};}}rep(x, 0, b / 2){db y = sqrt(b*b*1.0-x*x*1.0);if (fabs(y-(int)y)<=EPS){vb[++ cntB] = (pos){x, y};vb[++ cntB] = (pos){x, -y};vb[++ cntB] = (pos){y, x};vb[++ cntB] = (pos){y, -x};}}int ans = 0;rep(i, 1, cntA){rep(j, 1, cntB){pos ta = va[i], tb = vb[j];db d = sqrt((ta.x-tb.x)*(ta.x-tb.x)*1.0+(ta.y-tb.y)*(ta.y-tb.y)*1.0);if (fabs(c-d)<=EPS){ans = 1;break;}}if (ans){break;}}if (ans){puts("Yes");}if (!ans){puts("No");}}return 0;
}