Deploy the autobots
Autobots are instructed by Optimus Prime to mobilize in the form of a rectangular shape with each Autobot on each vertex of the rectangle region on a -”deployment area” (which may consist of one or more regions). This is done so as to take care of the inner rectangular area called “region”. However the rule states-“no two regions may overlap”. You have been asked to remove some regions from the “deployment area” so the remaining regions do not obscure each other. To keep the disturbance to the minimum level, you should remove the minimum number of regions to achieve this goal. You may not remove a region and place it in another position; all regions you leave in “deployment area” must be in their original position.
When you examined the “deployment area”, you noticed something very nice. Every region was placed on the deployment area by placing each autobot in the four corners. This was done in a very courteous manner since each autobot is guarding only the region it is holding.
The reason Optimus Prime wants your help because you are good at taking down a single region without disturbing the rest, even if that region is obscured by many others.
The first line consists of a single integer T indicating the number of test cases (about 25).
Each test case consists begins with a single integer n indicating the number of regions. The next n lines consist of 4 integers x0, x1, y0, and y1 satisfying x0 < x1 and y0 < y1. This means the region covers all points (x,y) satisfying x0 <= x <= x1 and y0 <= y <= y1.
As stated before hand, no corner of any region will intersect any other region anywhere. That is, if (x,y) is a corner point of one region and another region is described by x0, x1, y0, and y1, then we do not have x0 <= x <= x1 and y0 <= y <= y1.
Bounds: 1 <= n <= 100 and each integer in a region description fits in a signed 32 bit integer.
The output for each test case is a single line containing a single integer that is the maximum number of regions that can be left on the wall such that no two regions share a common point in the deployment area.
Input: 1 4 0 4 0 4 1 3 1 2 2 3 1 3 3 4 1 3 Output: 2
|Time Limit:||0.2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, 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