【题意】
给出三角形的三个边长，均是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(2*z)+eps); for (i=1;i<=mx;i+=2)//枚举本源勾股数组 { for (j=i+2;j<=mx;j+=2) { if (gcd(i,j)>1) continue; a=i*j; b=(j*j-i*i)/2; c=(j*j+i*i)/2; if (x%c==0) { 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==0) { 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(0,x));xx.PB(MP(x,0));xx.PB(MP(0,-x));xx.PB(MP(-x,0)); yy.PB(MP(0,y));yy.PB(MP(y,0));yy.PB(MP(0,-y));yy.PB(MP(-y,0)); for (i=0;i<xx.size();i++) { for (j=0;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 %I64d %I64d %I64d %I64d ",xx[i].X,xx[i].Y,yy[j].X,yy[j].Y); return 0; } } } printf("-1 "); return 0; }