OFFSTRAT - Problem Offensive Strategy

no tags 

Foo Football Club is a very offensive soccer team. Its coach is planning a new attack strategy.

In order not to change its image of offensive team, the coach wants to be sure that the new attack strategy is going to be strongly offensive. He is a very grumpy coach so he does not allow the players to make a pass that is not in the strategy sheet. In fact he is so mad that he does not allow the player who holds the ball to move.

An attack strategy is strongly offensive if each football pass position inside the field goes to another football pass position inside the field which is in the same distance or closer to the enemy line of goal, and also it should be possible to reach the enemy goal from every pass position described in the strategy sheet.


The first line of input consist of a number T (T <= 20) representing the number of test cases, then T test cases follow describing a strategy.

Each test case begins with two integers W and H (1 < W, H <= 100, also W and H are even integers) representing the width and height of the soccer field. The goal lines is the line x = w and the goal is gotten form a pass point (x, y) if it is possible reach the point (w, h/2) from (x, y).

These are followed by an integer number M (1 <= M < 1000000) the number of available passes in the strategy. The next M lines consist of four integer numbers x0, y0, x1, y1 (0 <= x0, x1 <= W and 0 <= y0, y1 <= H) representing the start position (x0, y0), and the end position (x1, y1) of an available pass in.


For each test case the output should consist of a single line containing “Yes” (without quotes) if the strategy is strongly offensive or “No” (without quotes) otherwise.



2 2 1
0 1 2 1

2 2 4
0 1 2 1
0 0 1 1
0 2 1 1
1 1 2 1


hide comments
Vipul Srivastava: 2022-04-03 11:39:09

My complexity is O(M) and I still get a TLE, doesn't make sense to me.

Added by:Paulo Costa
Time limit:1.238s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64