回分類題庫
h063: G.大野羊和小綿狼
關鍵字: NPSC 2009 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 10 Times / 9 Users | Submit : 15 Times / 10 Users | Accepted rate : 90%
題目加入時間 : 2012-11-04 02:09

Content: 简体中文

從前從前有很多的小綿狼和小綿羊, 每隻小綿狼每天吃一隻小綿羊並且過著幸福快樂的日子。小綿羊在長期受到了小綿狼的侵襲之後,某些小綿羊神奇地演化成大野羊,而這些大野羊的視野被自己的欲望所蒙蔽,因此只能看到視野內的東西,如果他看到小綿狼就會馬上把他吃掉。

現在給你今天 n 隻小綿狼、p 隻小綿羊和 q 隻大野羊的座標以及大野羊的視野 d。請問今天這 n 隻小綿狼能不能在不穿過大野羊的視野的前提之下都吃到一隻小綿羊並且活到明天。(距離算法為曼哈頓距離 |xi-xj|+|yi-yj| )。

Input:

第一個數字表示測資有幾筆。
每組測資第一行依序為 n, p, q, d ( 0 <= n, p, q, d <= 100 )。之後 n 行 xi, yi 為小綿狼的座標。( 0<= xi, yi <= 1000)
接下來 p 行 xi, yi 為小綿羊的座標。( 0<= xi, yi <= 1000)
接下來 q 行 xi, yi 為大野羊的座標。( 0<= xi, yi <= 1000)
小綿狼、小綿羊和大野羊座標不會重複。

Output:

每組測資輸出一行。yes 表示今天這 n 隻小綿狼都能吃到一隻小綿羊並且活到明天。no 表示不行。

第一組測資為 no;因為小棉狼在 (0,0),大野羊在 (1,1),這隻小棉狼將會被大野羊吃掉而活不到明天。

第二組測資為 no; 因為雖然兩隻小綿狼都不會被大野羊吃掉,但是他們的食物只有一隻小綿羊;因此,這兩隻小綿狼不能都吃到一隻小綿羊。

三組測資為 no; 因為小棉狼在 (0,0),大野羊在 (5,0),他們之間的距離為 |0-0|+|5-0|=5 <= 5=d,所以這隻小棉狼會被大野羊吃掉。

第四組測資為 yes; 這隻小棉狼不但不會被吃掉而且還能夠吃到一隻小綿羊。

第五組測資為 no; 因為雖然這隻小棉狼不會被大野羊吃掉,但是因為他不能被大野羊看到不然會被吃掉,所以他沒辦法穿過大野羊的視野範圍; 而在他的行動範圍內又沒有其他小綿羊,因此他吃不到任何小綿羊。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5
1 2 1 5
0 0
5 6
10 13
1 1
2 1 0 5
0 0
5 6
1 1
1 1 1 5
0 0
1 1
5 0
1 1 1 5
0 0
1 1
6 0
1 1 4 5
5 5
50 50
0 0
0 9
9 0
9 9

Sample Output :

no
no
no
yes
no

Hint :

Author :

NPSC 2009 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum