TopCoder

8e7
$\huge X語言專家 $(TIOJ 1269)

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

25.0% (3/12)

Tags

Description

在一個無限延伸的座標平面上,一個格子點(x,y座標都是整數的頂點)上住著一顆蕃茄,所有的格子線(x,y座標其中一個是整數的點所形成的許多直線)都是可以通行的道路。可是現在突然發生了某些意外,一些格子點被堵住了。

這天,大頭蕃正準備邀請走路總時間不超過S秒的所有蕃茄到他的家(0,0)的位置上作客。他知道住在沒有被堵住的格子點上的蕃茄,沿著格子線走一格邊長的距離需要一秒鐘(轉彎所花的時間可以不計,也假設蕃茄不佔用任何空間,所以不必考慮「塞蕃茄」的問題)。

所有的蕃茄走到大頭蕃的家(如果到得了的話),都一定會走最短路徑。

所有蕃茄,被大頭蕃依照屬性歸類為紅色蕃茄,以及綠色蕃茄。然而分類方法是以每顆蕃茄與大頭蕃的家的最短距離來計算。若最短距離是偶數,那麼那顆番茄的顏色就是紅色,否則是綠色。

請問大頭蕃分別能夠邀請多少紅色、綠色的蕃茄呢?

被堵住的格子點上沒有蕃茄,也沒有任何蕃茄能夠經過被堵住的格子點。

Input Format

輸入檔可能包含多筆測試資料,以EOF結束輸入。
每筆測試資料的第一列包含兩個整數 B, S(0<=B<=10,000;1<S<=10,000,000)分別代表被堵住的格子點數以及最久走路時間限制秒數。
接下來的B列每列有兩個整數,代表該座標是被堵住的,座標值的絕對值不會超過1000。
座標的原點(0,0),也就是大頭蕃的家,不會被堵住。

Output Format

對於每筆測試資料請輸出兩個整數,代表沒被堵住的格子點上有多少紅色、綠色的蕃茄能夠被大頭蕃邀請。

Sample Input 1

0 2
4 5
-1 1
0 -1
0 1
1 0
4 50000
1 1
-1 -1
1 -1
-1 1

Sample Output 1

9 4
10 16
2500099997 2500000000

Hints

Problem Source

原TIOJ1207 / TIOJ 2008例行賽02-Elite (prob I)。Croatian Olympiad in Informatics 2007, SABOR。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1