在一個無限延伸的座標平面上,一個格子點(x,y座標都是整數的頂點)上住著一顆蕃茄,所有的格子線(x,y座標其中一個是整數的點所形成的許多直線)都是可以通行的道路。可是現在突然發生了某些意外,一些格子點被堵住了。
這天,大頭蕃正準備邀請走路總時間不超過S秒的所有蕃茄到他的家(0,0)的位置上作客。他知道住在沒有被堵住的格子點上的蕃茄,沿著格子線走一格邊長的距離需要一秒鐘(轉彎所花的時間可以不計,也假設蕃茄不佔用任何空間,所以不必考慮「塞蕃茄」的問題)。
所有的蕃茄走到大頭蕃的家(如果到得了的話),都一定會走最短路徑。
所有蕃茄,被大頭蕃依照屬性歸類為紅色蕃茄,以及綠色蕃茄。然而分類方法是以每顆蕃茄與大頭蕃的家的最短距離來計算。若最短距離是偶數,那麼那顆番茄的顏色就是紅色,否則是綠色。
請問大頭蕃分別能夠邀請多少紅色、綠色的蕃茄呢?
被堵住的格子點上沒有蕃茄,也沒有任何蕃茄能夠經過被堵住的格子點。
輸入檔可能包含多筆測試資料,以EOF結束輸入。
每筆測試資料的第一列包含兩個整數 B, S(0<=B<=10,000;1<S<=10,000,000)分別代表被堵住的格子點數以及最久走路時間限制秒數。
接下來的B列每列有兩個整數,代表該座標是被堵住的,座標值的絕對值不會超過1000。
座標的原點(0,0),也就是大頭蕃的家,不會被堵住。
對於每筆測試資料請輸出兩個整數,代表沒被堵住的格子點上有多少紅色、綠色的蕃茄能夠被大頭蕃邀請。
原TIOJ1207 / TIOJ 2008例行賽02-Elite (prob I)。Croatian Olympiad in Informatics 2007, SABOR。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |