BOBALLS2  Bouncing Balls II
"Behold, my queen", said the jester, "the great Bouncing Ball Bowl!" The queen boredly waved her hand and sarcastically replied: "Let the fun begin!". And the fun begun! The jester spoke a magic word and all the colorful balls in his bowl started to roll and bounce, creating interesting pictures.
The queen watched vividly for a few minutes, but then she started to be bored again. "Just wait a moment, Your Majesty, in a minute they'll…" started the jester, but the queen interrupted: "I'm a queen! I don't want to wait! Can't you just fast forward it or something?"
Problem specification
The jester's box is an X * Y (1<= X, Y <=5000)rectangle. The rectangle contains N(N <=3001) small balls. At any moment, each ball is travelling at the same speed in one of the four diagonal directions.
The movement of the balls is continuous and for the purpose of this problem we may consider them to be points. When two or more balls meet, they bounce in a way described below.
Your task is to determine the state of the box at given moments in time.
Bouncing specification
Bouncing does not change the speed of the balls. Following images show how the balls bounce off each other, and also off walls. Each image can be rotated arbitrarily. For example, the first image shows that whenever two balls meet at a right angle, they bounce and depart at a right angle again. One particularly tricky case is shown in the third image.
Input specification
The input starts with a line containing the dimensions X and Y of the box. We will use a coordinate system with axes parallel to the sides of the box, (0,0) at one of the corners and (X,Y) at the opposite corner.
The second line contains the number of balls N.
Each of the next N lines contains four integers x,y,vx,vy, where (x,y) are the coordinates of one ball at time 0 and (vx,vy) is its current velocity vector. (Each ball will be strictly inside the box and for each ball both the absolute values of vx and vy will be equal to 1. No two balls will start at the same place.)
The following line contains the number of queen's requests M.(1<= M <=20)
On the last line there are M numbers t_{1},…,t_{M} – the points in time the queen wants to see. These numbers will be less than 10^{12}.
Output specification
As a solution to this problem, we expect a file with M blocks, with the ith block describing the situation at time t_{i}.
Each block must contain N lines, and each line must contain the x and y coordinates of one ball. The balls in each block must be sorted – primarily by to their first, secondarily by their second coordinate at that point in time.
You may output an empty line between the blocks.
Example
Input: 6 4 4 1 2 1 1 5 2 1 1 2 1 1 1 3 1 1 1 1 4 Output: 1 3 3 2 5 2 6 3
Note that the balls that start at (2,1) and (3,1) bounce off each other at a noninteger point in time.
hide comments
Rishav Goyal:
20160831 11:53:12
yeah, implementation sucks but!!!!! 

sumitsinghnit:
20160821 09:08:46
Nice question. Requires observation. After that, piece of cake.

Added by:  Fudan University Problem Setters 
Date:  20090531 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  IPSC 2009 