POINTS - Point Nesting
A point in 3D A (ax, ay, az) is said to nest another point B (bx, by, bz), iff bx <= ax AND by <= ay AND bz <= az. Given a set of 3D points, find a nesting sequence using maximal number of points. A sequence P0, P1, P2, ... is said to be a valid nesting sequence iff, P1 nests P0, P2 nests P1 and so on. Please note there could be duplicate points, and each input point must be used at most once while creating the sequence.
Input
First line contains the number of test cases T.
Each test case starts with n - the number of points. (0 < n <= 100,000)
The next n lines give the input points.
Output
For each test case print one integer saying the length of the longest nesting sequence.
Example
Input: 2 4 930887 692778 636916 747794 238336 885387 760493 516650 641422 202363 490028 368691 10 897764 513927 180541 383427 89173 455737 5212 595369 702568 956430 465783 21531 722863 665124 174068 703136 513930 979803 634023 723059 133070 898168 961394 18457 175012 478043 176230 377374 484422 544920 Output: 2 3
hide comments
Srivatsan B:
2009-05-05 15:15:26
I think this problem deserves to be in the main set, not the tutorial set. |
|
Srivatsan B:
2009-05-05 04:26:51
I think the test data is a bit weak.
|
Added by: | Prasanna |
Date: | 2008-03-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | CMI Local Contest |