问题 4727 --2009年 珠海赛 Insect World

4727: 2009年 珠海赛 Insect World

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

The ants and the aphids live together happily in a very large land. But another insect, 

ladybug, also lives in this land and brings great danger to the other twoOne task of 

the ants is driving the ladybugs away.

We number the n ants with 1, 2 , … n. Wherever the ladybugs is sitting, the ants’ 

actions are following those principles:

 

1) All the ants will choose a shortest path moving to the ladybug, and the ants can 

move only one step to the adjacent points (only forwards, backwards, left, right) 

at one time.

2) The ant whose path is the shortest will be the attacker who can move to ladybug. 

If there is a tie the smaller numbered ant is the attacker. While the attacker 

moves to the ladybug, the others will keep unmoved.

But after the ladybug has been driven away, it will fly back to another square. So the 

ants will continue their job.

Now your task is giving you the initial positions of the ants and the position of 

every time the ladybug sitting in, can you tell me the final positions of the ants. 

And you should also need to tell how many times each ant drives the ladybug away from the 

land.

输入

There are more than one test cases, for every test case, the first line have two integers, 

n,m (1<=n, m<=100) , which means the number of the ants and the time the ladybugs 

landing on the land. The following n lines are the initial position of the ants, 

presented by the (Xi, Yi), -10000<=Xi, Yi<=10000; then the following m lines are the 

positions of the ladybug lands each time (X,Y) -10000<=X, Y<=10000.

输出

For each test case, it consist of n+1 lines, the first line is as follows:

Test #:

Then follows n lines, on the line i, is the final position (x, y) of the ant i and the 

times this ant drives the ladybug away from the land.

样例输入

2 2<br/>3 3<br/>4 4<br/>1 2<br/>3 2

样例输出

Test 1:<br/>3 2 2<br/>4 4 0

提示

undefined

来源

[提交][状态]