当前位置:网站首页>(lightoj - 1323) billiard balls (thinking)
(lightoj - 1323) billiard balls (thinking)
2022-07-06 16:23:00 【AC__ dream】
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;
}
边栏推荐
- Calculate the time difference
- Flag framework configures loguru logstore
- Flask框架配置loguru日志库
- antd upload beforeUpload中禁止触发onchange
- Suffix expression (greed + thinking)
- Codeforces Round #798 (Div. 2)A~D
- F - birthday cake (Shandong race)
- Borg maze (bfs+ minimum spanning tree) (problem solving report)
- Opencv learning log 26 -- detect circular holes and mark them
- Interval sum ----- discretization
猜你喜欢
window11 conda安装pytorch过程中遇到的一些问题
The concept of C language array
1529. Minimum number of suffix flips
860. Lemonade change
pytorch提取骨架(可微)
QT模拟鼠标事件,实现点击双击移动拖拽等
1605. Sum the feasible matrix for a given row and column
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
< li> dot style list style type
QT style settings of qcobobox controls (rounded corners, drop-down boxes, up expansion, editable, internal layout, etc.)
随机推荐
1689. Ten - the minimum number of binary numbers
Borg maze (bfs+ minimum spanning tree) (problem solving report)
B - Code Party (girls' competition)
Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
Problem - 1646C. Factorials and Powers of Two - Codeforces
Classic application of stack -- bracket matching problem
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
树莓派4B安装opencv3.4.0
Kubernetes集群部署
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
(lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)
本地可视化工具连接阿里云centOS服务器的redis
Summary of FTP function implemented by qnetworkaccessmanager
OneForAll安装使用
Raspberry pie csi/usb camera uses mjpg to realize web camera monitoring
Flask框架配置loguru日志库
E. Breaking the Wall
C language is the watershed between low-level and high-level
C basic grammar
7-1 understand everything (20 points)