A Home for Chef
All submissions for this problem are available.
Our hardworking chef is bored of sleeping in his restaurants. He has decided to settle down. The first thing he must do is to find a suitable location to build a palatial home.
Think of the city as a two-dimensional grid. There are N restaurants in the city. Each of the chef's restaurant is a point denoted by (X , Y). A house can be located at a grid point (R, S) if the sum of the distances between this point and each of the restaurants is as small as possible. Find the number of possible house locations in the city to help out chef build a home.
More than one restaurant can be located at the same point.
Houses and restaurants can be located at the same point.
Every house must have integer co-ordinates. In other words, R and S are integers.
The distance between two points (A,B) and (C,D) is |A-C| + |B-D|. Here |X| is the absolute function.
First line in the input contains T, number of test cases.
First line of each test case contains N, number of restaurants.
Each of the next N lines contain two integers X and Y separated by a space.
T <= 100
N <= 10^3
-10^8 <= X <=10^8
-10^8 <= Y <=10^8
The number of possible locations (grid points) where houses can be built.
Input: 3 5 0 0 -1 0 1 0 0 1 0 -1 5 31 11 30 -41 20 14 25 18 25 38 2 0 0 1 1 Output: 1 1 4
|Tags||may12, medium, rosyish|
|Time Limit:||0.352542 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.