(lightoj - 1323) billiard balls (thinking)

Topic link ：Billiard Balls - LightOJ 1323 - Virtual Judge

The question ： It starts with a rectangle , Then there are some balls in the rectangle , Every ball is moving , The direction of movement is southeast , The northeast , southwest , Four directions in the northwest , for instance , Suppose the coordinates of the current ball are (x,y), Then the ball will become (x+1,y+1), The ball may collide with the ball during its movement , After the collision, the two balls move in the opposite direction at the original speed , Ask about the process k The position of the ball in seconds , according to x First priority ,y Sort for the second priority , The smaller, the better .（ The specific movement method is combined with the schematic diagram in the topic ）

I talked about this kind of collision problem in a previous title of the Blue Bridge Cup , After two balls collide, they move in reverse at the same speed, which is equivalent to passing through the collided sphere at the original speed , Besides, the final output is in order , So it doesn't matter the number , We also use a technique here, that is, we decompose the direction of oblique motion into x Axis and y Axis , Because it is convenient for us to deal with , Exercise meets the complex , So we deal with each direction separately , Finally, it is the last position . Let's see how to deal with motion in one direction , For example, the current ball moves on the length of the rectangle , The position is x, Long for l, Exercise time is t, At this time, we need to discuss it according to the situation ( Here's the picture )

The first situation is t+x<=l That is to say, the small ball will not collide with the boundary , Then our direct final position is t+x

The second situation is t+x<=2*len, That is to say, the ball will only touch the boundary , Will not touch the left boundary , At this time, it is also easy to find by observing the diagram , The final position is 2*len-(x+t)

The third is also the most complex , The ball will hit the left and right boundaries many times , Then at this time, we can first calculate the time it takes to encounter the left boundary for the first time 2*len-pos, Subtract this time from the total time , And then to 2*len Remainder , Because every time in this process 2*len Time will return to the left border , Then call the original function again to solve the problem . The corresponding code is attached below ：

int UP(int len,int t,int pos)
{
	if(pos+t<=len) return pos+t;
	else if(pos+t<=2*len) return 2*len-(pos+t);
	return UP(len,(t+pos)%(2*len),0);
}

  With the above basis, it will be easier to calculate the motion in the opposite direction , The following two situations are introduced

The first is the distance to the left x<=pos, Then it's easy to know the final position is pos-x

If not for the above , Then the ball will collide with the left boundary , Then we use the total time minus the time spent walking to the left boundary as the time spent in the new movement , And set the position at this time as the position of the left boundary , Suddenly found that the ball is now walking to the right , At this time, we can call the function written above to perform the operation directly

  This step corresponds to the code ：

int DOWN(int len,int t,int pos)
{
	if(pos>=t) return pos-t;
	else
		return UP(len,t-pos,0);
}

That's all for the train of thought , The following can be understood in combination with the code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1003;
struct point{
	int x,y;
}p[N];
bool cmp(point a,point b)
{
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
int UP(int len,int t,int pos)
{
	if(pos+t<=len) return pos+t;
	else if(pos+t<=2*len) return 2*len-(pos+t);
	return UP(len,(t+pos)%(2*len),0);
}
int DOWN(int len,int t,int pos)
{
	if(pos>=t) return pos-t;
	else
		return UP(len,t-pos,0);
}
int main()
{
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		printf("Case %d:\n",_);
		int l,w,n,k;
		scanf("%d%d%d%d",&l,&w,&n,&k);
		char op[5];
		for(int i=1;i<=n;i++)
		{
			int x,y;
			scanf("%d%d%s",&x,&y,op);
			if(op[0]=='N') p[i].y=UP(w,k,y);
			else p[i].y=DOWN(w,k,y);
			if(op[1]=='E') p[i].x=UP(l,k,x);
			else p[i].x=DOWN(l,k,x);
		}
		sort(p+1,p+n+1,cmp);
		for(int i=1;i<=n;i++)
			printf("%d %d\n",p[i].x,p[i].y);
	}
	return 0;
}