【题意】
给出三角形的三个边长，均是10^7以内的整数，问三角形的三个角的坐标是否能均是整数，输出其中任意一个解。
【题解】
一开始想的是枚举一条边的横坐标，然后通过勾股定理以及算角度求出其他点的坐标，再判断是否符合条件。
亲测TLE
直到知道了本源勾股数组的构造方法。。。
每个本源勾股数组(a,b,c)满足a*a+b*b=c*c，其中a为奇数，b为偶数。。
枚举s,t（1<=t<s，且它们是没有公因数的奇数）
a=st b=(s*s-t*t)/2 c=(s*s+t*t)/2
因为最大数c=(s*s+t*t)/2 所以最多枚举到sqrt(2*c)即可。
假设三角形的三个点分别为p,q和r，
我们先固定一个点为p(0,0)，另外一个点q与它的距离是x，还有一个点r与它的距离是y。那么q的距离与r的距离一定是z
我们枚举勾股数组，如果勾股数组(a1,b1,c1)的c1，也就是最大的那个数，等于x，那么x的坐标为(a1,b1)【当然也可以是(a1,-b1),(-a1,b1),(-a1,-b1)，均需要枚举，下同】
然后枚举c等于y的勾股数组，(a2,b2,c2)，那么r点坐标为(a2,b2) 【可以事先把这些坐标预处理出来，放入vector中】
接下来判断两坐标是否相距为z即可。
注意通过这种方法求出来的勾股数组的a是奇数，也就是说它们的倍数 (i*a,i*b,i*c)，i是一个正整数，并不会被求出来，我们要求的是i*c==x，那么只要满足x mod c=0我们就可以把勾股数组乘以x/c，加入备选选项中。
注意(0,x) (0,-x) (x,0) (-x,0)以及(0,y) (0,-y) (y,0) (-y,0) 不会在枚举本源勾股数组中出现，所以需要自己手动判断。
#include<bits/stdc++.h>
#define eps 1e-9
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 1005
#define MAXM 40005
#define INF 0x3fffffff
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define lc (k<<1)
#define rc ((k<<1)1)
using namespace std;
typedef long long LL;
LL i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag;
LL z;
LL mx,sum,a,b,c;
vector <pair<LL,LL> > xx,yy; LL gcd(LL x, LL y)
{
return y ? gcd(y, x % y) : x;
} int main()
{
scanf("%I64d%I64d%I64d",&x,&y,&z);
if (x>y) swap(x,y);
if (y>z) swap(y,z);
if (x>y) swap(x,y);
mx=(LL)(sqrt(*z)+eps); for (i=;i<=mx;i+=)//枚举本源勾股数组
{
for (j=i+;j<=mx;j+=)
{
if (gcd(i,j)>) continue;
a=i*j;
b=(j*j-i*i)/;
c=(j*j+i*i)/;
if (x%c==)
{
xx.PB(MP(a*x/c,b*x/c));
xx.PB(MP(a*x/c,-b*x/c));
xx.PB(MP(-a*x/c,b*x/c));
xx.PB(MP(-a*x/c,-b*x/c));
xx.PB(MP(b*x/c,a*x/c));
xx.PB(MP(b*x/c,-a*x/c));
xx.PB(MP(-b*x/c,a*x/c));
xx.PB(MP(-b*x/c,-a*x/c));
}
if (y%c==)
{
yy.PB(MP(a*y/c,b*y/c));
yy.PB(MP(a*y/c,-b*y/c));
yy.PB(MP(-a*y/c,b*y/c));
yy.PB(MP(-a*y/c,-b*y/c));
yy.PB(MP(b*y/c,a*y/c));
yy.PB(MP(b*y/c,-a*y/c));
yy.PB(MP(-b*y/c,a*y/c));
yy.PB(MP(-b*y/c,-a*y/c));
}
}
}
xx.PB(MP(,x));xx.PB(MP(x,));xx.PB(MP(,-x));xx.PB(MP(-x,));
yy.PB(MP(,y));yy.PB(MP(y,));yy.PB(MP(,-y));yy.PB(MP(-y,)); for (i=;i<xx.size();i++)
{
for (j=;j<yy.size();j++)
{
if ((xx[i].X-yy[j].X)*(xx[i].X-yy[j].X)+(xx[i].Y-yy[j].Y)*(xx[i].Y-yy[j].Y)==z*z)
{
printf("0 0\n%I64d %I64d\n%I64d %I64d\n",xx[i].X,xx[i].Y,yy[j].X,yy[j].Y);
return ;
}
}
}
printf("-1\n");
return ;
}