| Submit | All submissions | Best solutions | Back to list |
CRAN03 - Howard The Saviour |
Howard is now an astronaut. After a successful journey to the space station, he is now headed towards Mars this time for yet another interesting task. But this task of his will save the humanity. Some alien pirates have placed bombs on a very large rectangular grid. Some of the bombs are Master bombs. Master bombs have at least one bomb on their left hand side, right hand side, above and below their position.
As soon as Howard reaches Mars he notes down the coordinates of the bombs that have been planted. Now he has to count the Master bombs that have been placed on Mars.
Given position of all the bombs help Howard to count the number of Master Bombs.
Input
First line contains t, the number of test cases.
The next line contains n, the number of bombs in the grid.
Next n lines contain the coordinates of the bombs (xi, yi).
Output
Output the number of Master bombs.
Constraints
1<=t<=10
1<=n<=500
0<= xi, yi<=200
Example
Input: 2
5
1 1
0 1
1 0
6 1
1 9
8
1 1
4 2
3 1
1 2
0 2
0 1
1 0
1 3
Output: 1
2
| Added by: | CSI |
| Date: | 2013-02-16 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
hide comments
|
2018-06-21 08:57:58
NlogN is relatively easy to conceive but kinda tedious to get right. Took me 45 mins to debug the damn thing.. Shame about the constraints, with the ones Ehor proposed it would make a good classical still solvable in slower languages. |
|
|
2013-02-24 02:26:02 Kevin Sebastian
this is really annoying...if a problem should be in tutorial it should be put there already not stay as classical problem for a long time |
|
|
2013-02-23 22:06:12 :D
Yes the problem is trivial. As Ehor said, this can be in classical, but only a version with much bigger constraints. O(N^2) and O(maxX * maxY) should definitively fail. O(N * logN) should be the required complexity. |
|
|
2013-02-19 19:24:04 STARK
i am getting correct answer for the sample test cases....are there any tricky part which i am missing in this ques ?? or please check my solution...and guide me with some hint of my mistake |
|
|
2013-02-18 11:58:29 Ehor Nechiporenko
With such consraints this problem looks tutorial. It's much more interesting to resolve this problem, when n = 10^6 and xi,yi <= 10^9. |
RSS