本文主要是介绍数学、半几何，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=64147#problem/I
题目意思：
输入三角形的三条边长，均为整数，范围 | |<=1e7。问是否存在整数点坐标满足这个三角形。如果存在，输出任意一组解。
| input | output |
|---|---|
4 3 5 | 0 0 3 4 3 0 |
10 17 21 | 0 0 0 21 -8 15 |
100 100 100 | -1 |
分析：刚开始用几何思想去做，先找出一组解，尽管不是整数点，但是rotate旋转，看是否有解，我还用了3条边的全排列顺序。结果不是wa就是TLE。==
中午相当测试下半径1e7的圆有多少整数点，发现100不到，<<100个，如此就想暴力了。把圆上的点都预处理出来，在暴力2个圆上的点，判断另一条边的长度是否有解。一发A了。
AC代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define rt return
#define bk break
#define ct continue
#define sf scanf
#define pf printf
#define ms memset
#define si(n) sf("%d",&n)
#define pi(n) pf("%d\n",n)
#define REP0(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,s,n) for(int i=s;i<=(n);i++)
#define db double
#define pb push_back
#define LL long long
#define INF 0x3fffffff
#define eps 1e-8
#define PI acos(-1)
#define maxn 1001
#define op operator
using namespace std;
struct node{db x,y;node(db a=0,db b=0){x=a,y=b; }node op - (node a){rt node(x-a.x,y-a.y); }db dis(){rt sqrt(x*x+y*y); }void out(){pf("%d %d\n",(int)x,(int)y); }
};
int sig(db x){rt (x>eps)-(x<-eps); }
int solve(node p[],int R){//将半径为R的圆上的整数点保存在p数组中，返回个数db r=R*1.0;int cnt=0;p[cnt].x=0,p[cnt].y=r;cnt++;p[cnt].x=0,p[cnt].y=-r;cnt++;p[cnt].x=r,p[cnt].y=0;cnt++;p[cnt].x=-r,p[cnt].y=0;cnt++;for(int x=1;x<r;x++){//第一象限db y=sqrt(r*r-1.0*x*x);if(sig(y-(int)y)==0){p[cnt].x=x,p[cnt].y=y;cnt++;p[cnt].x=x,p[cnt].y=-y;cnt++;p[cnt].x=-x,p[cnt].y=y;cnt++;p[cnt].x=-x,p[cnt].y=-y;cnt++;}}rt cnt;
}
bool judge(node p[],int cnt1,node q[],int cnt2,db r){for(int i=0;i<cnt1;i++){for(int j=0;j<cnt2;j++){if(sig((p[i]-q[j]).dis()-r)==0){pf("0 0\n");p[i].out();q[j].out();rt true;}}}rt false;
}
int main(){db a,b,c;while(~sf("%lf%lf%lf",&a,&b,&c)){node PA[1001],PB[1001],PC[1001];int cntA=solve(PA,a);int cntB=solve(PB,b);int cntC=solve(PC,c);if(judge(PA,cntA,PB,cntB,c)==false)if(judge(PA,cntA,PC,cntC,b)==false)if(judge(PB,cntB,PC,cntC,a)==false)puts("-1");}rt 0;
}
//如果求圆内以及圆上的个数，一样可以求个数，但是点数很多。
WA、TLE代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define rt return
#define bk break
#define ct continue
#define sf scanf
#define pf printf
#define ms memset
#define si(n) sf("%d",&n)
#define pi(n) pf("%d\n",n)
#define REP0(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,s,n) for(int i=s;i<=(n);i++)
#define db double
#define pb push_back
#define LL long long
#define INF 0x3fffffff
#define eps 1e-10
#define PI acos(-1)
#define maxn
#define op operator
using namespace std;
int sig(db x){rt (x>eps)-(x<-eps); }
struct node{db x,y;node(){}node(db a,db b){x=a,y=b;}node op - (node a){rt node(x-a.x,y-a.y); }db op * (node a){rt x*a.x+y*a.y; }db op ^ (node a){rt x*a.y-a.x*y; }db dis(){rt sqrt(x*x+y*y); }node rota(db d){node a;a.x=x*cos(d)-y*sin(d);a.y=y*cos(d)+x*sin(d);rt a;}void out(){pf("%d %d\n",(int)x,(int)y);}
};
bool check(node B){if(sig(B.x-(int)B.x)==0&&sig(B.y-(int)B.y)==0)rt true;rt false;
}
bool solve(db a,db b,db c){node A(0,0);node C(b,0);node tmp(c,0);db d=acos((b*b+c*c-a*a)/(2.0*b*c));node B=tmp.rota(d);db r=b;for(int x=r;x>=1;x--){db y=sqrt(r*r-x*x);if(sig(y-(int)y)!=0)continue;db ang=atan(y/x);node B1=B.rota(ang);node C1=C.rota(ang);if(check(B1)&&check(C1)){A.out();B1.out();C1.out();rt true;}}rt false;
}
int main(){double num[3];while(~sf("%lf%lf%lf",&num[0],&num[1],&num[2])){sort(num,num+3);bool ok=false;do{db a=num[0],b=num[1],c=num[2];if(solve(a,b,c)){ok=true;break;}}while(next_permutation(num,num+3));if(ok==false)pf("-1\n");}rt 0;
}
这篇关于数学、半几何的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
