一道简单的几何题：HDOJ5114

对于有模板和懂数学的大神来说，几何题都是水题吧


给两个点的坐标，初始化的速度方向向量为（1，1），两个点在n*m的矩阵中移动，遇到边界没有能量损失反弹前进，问这两个点是不是会在某个点相遇？求出相遇点的坐标。


几何题都得懂原理才能写

首先得明白有几种情况相遇：

1.两个点，速度方向向量互为相反，即相向而行，且x方向的差量与y方向的差量相同

2.两个点，同x轴，x轴方向向量相同，且如果能相遇，相遇点的y值在界内

3.两个点，同y轴，y轴方向向量相同，且如果能相遇，相遇点的x值在界内


所以，两个点拆成4个方向向量来做是最好的


如何模拟呢？n最大100000，矩形4条边，不妨直接暴力400000次，逐个以公式带入判断会不会相同

具体细节看代码


//第一个点坐标为（x1，y1） 
//第一个点方向向量为（fx11，fx12） 
//同理第二个点

//注意细节，y1这个变量在math.h中有过定义
//平时写程序尽量避免使用
//G++和C++编译器有区别
//在不怕TLE的情况下用G++更好 
int x1,y1,x2,y2,t,fx11,fx12,fx21,fx22,Move,n,m;
double ansx,ansy;

void change_dir(){
	//第一个点到达最右边并且x方向上速度向右
	//第一个点到达最左边并且x方向上速度向左 
	if ((x1==n&&fx11>0)||(x1==0&&fx11<0)) fx11=-fx11;
	//之后同理
	if ((y1==m&&fx12>0)||(y1==0&&fx12<0)) fx12=-fx12;
	if ((x2==n&&fx21>0)||(x2==0&&fx21<0)) fx21=-fx21;
	if ((y2==m&&fx22>0)||(y2==0&&fx22<0)) fx22=-fx22;
}

int main(){
	//input; 
	int i;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
		fx11=fx12=fx21=fx22=1;
		//如果有点一开始就在边界上而且恰好往边界方向有分速度
		//那么刚出发时就需要对速度矢量进行更改 
		change_dir();
		//n最大为100000，考虑到矩形有4条边
		//相当于把边界上的所有点枚举一遍 
		for(i=1;i<=410000;i++){
			//Case1:两个点迎面相遇
			//条件为：两边方向迎面，而且x和y轴上相差的距离相等 
			if (abs(x1-x2)==abs(y1-y2)&&(x2-x1)/fx11>0&&(y2-y1)/fx12>0
				&&(x1-x2)/fx21>0&&(y1-y2)/fx22>0){
					ansx=(x1+x2)/2.0;
					ansy=(y1+y2)/2.0;
					break;
				}
			//Case2:两个点在同一纵轴上
			//那么速度方向需要时反的，并且在相遇时候不能够走出界
			if (x1==x2&&(y2-y1)/fx12>0&&(y1-y2)/fx22>0&&fx11==fx21
				&&(x1+fx11*abs(y2-y1)/2.0>=0)&&(x1+fx11*abs(y2-y1)/2.0<=n)){
					//在同一纵轴上，y坐标取平均值为相遇点
					//根据y的变化算出两个点的运动时间，进而求x
					ansx=x1+fx11*abs(y2-y1)/2.0;
					ansy=(y1+y2)/2.0;
					break;
				}
			//Case3:同理Case2,两个点在同一横轴上 
			if (y1==y2&&(x2-x1)/fx11>0&&(x1-x2)/fx21>0&&fx12==fx22
				&&(y1+fx12*abs(x2-x1)/2.0>=0)&&(y1+fx12*abs(x2-x1)/2.0<=m)){
					ansx=(x1+x2)/2.0;
					ansy=y1+fx12*abs(x2-x1)/2.0;
					break;
				}
			//如果三种Case都没有发生
			//那么肯定会遇到某个点在某个方向上撞墙的情况
			//所以找到从现在到最近撞墙的时间
			//进一步修改点的位置和运动方向矢量
			//因为速度大小是（1，1）
			//所以直接根据距离算时间就好，判断一下运动方向 
			if (fx11>0) Move=n-x1;
			else Move=x1;
			if (fx12>0) Move=min(Move,m-y1);
			else Move=min(Move,y1);
			if (fx21>0) Move=min(Move,n-x2);
			else Move=min(Move,x2);
			if (fx22>0) Move=min(Move,m-y2);
			else Move=min(Move,y2);
			
			//到达边界之后马上修改运动方向 
			x1+=Move*fx11;
			y1+=Move*fx12;
			x2+=Move*fx21;
			y2+=Move*fx22;
			change_dir();
		} 
		printf("Case #%d:\n",Case);
		if (i==410001){
            puts("Collision will not happen.");
            continue;
		}
		else printf("%.1lf %.1lf\n",ansx,ansy);
	}
	return 0;
}