The 7th(2012) ACM Programming Contest of HUST - Preliminary Contest

From: 2012-11-17 12:00:00 To: 2012-11-17 17:00:00 Now: 2017-09-22 06:48:56 Status: Public

E - Deadly Disease

Time Limit: 2s Memory Limit: 64MB

Submissions: 43 Solved: 15
Description
Queen of honey was deeply shocked when she heard the news that some rooms in her honeycomb is infected with serious virus. To make things worse, each infected room will infect all the rooms which share an edge with it in a second. Because she is so sweet that you think you should help her. however, due to the fact that you do not know much about virus, you decide to be ready to tell her, how many rooms in her honeycomb will be infected in K(0<=K<=10^7) seconds.
Input
First comes an integer T (T<=50), indicating the number of test cases. For each test case, there is two integers N and K. N indicates how many rooms are initially infected, then comes the coordinates of the initially infected rooms, they are represent as (i,j) (0<=i,j<=30). One room can only be infected once and no two coordinates will be the same. Queen's honeycomb should be considered infinitely large.

Coordinates are calculated in this way:
Output
A single integer represent the total number of infected rooms after K seconds.
Sample Input
2
1 2 0 0
2 1 0 0 1 2
Sample Output
19
13
Hint


Source
Problem Setter : Han Yin