Divide And Rule
All submissions for this problem are available.
East India company wants to eliminate all the pirates of the Carribbean. Lord Cutler Beckett has come up with a brilliant plan to crush all that's left of the pirates. Consider the whole sea of caribbean as a grid of infinite width and length, Beckett decides that he will use the oldest and the greatest strategy of all times - Divide and Rule. The sea contains N islands. Beckett has analysed the entire Carribean and marked the coordinates of each island present as (Xi,Yi) . The islands are assumed to be a point lying exactly on the grid point.
To destroy the pirates, at each pirate island he will construct two mutually perpendicular infinite length fences parallel to x and y axis crossing each other only at the island itself. This will create many partitions of the sea which will then be attacked separately to outpower the pirates. Fences constructed may overlap or cut each other but each fence extends to the infinity in both X and Y direction. Only partitions with non-zero area will be considered, thus all the overlapping fences need to be considered as one fence only.
The Beckett needs to train his huge army in a number of battalions to kill the pirates. One battalion can attack one and only one partition of the grid. The battalions are trained enough to beat any number of pirates, thus they always win in their partition. Your task is to calculate the number of battalions to be trained to make the pirate race extinct.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case gives the number of islands N. The next N lines will contain two integers, Xi and Yi denoting the coordinates of the ith island.
For each test case, output a single integer representing the number of battalions which will have to be trained by Beckett.
- 1 <= T <= 10
- 0 <= N <= 10000
- -100000 <= Xi , Yi <= 100000
Input 2 2 2 2 3 3 2 2 2 3 2
Output 9 6
In the first test case there will be 9 partitions as shown in the figure below
|Time Limit:||0.131579 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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