SKYLINE2 - Draw Skyline Graph


Once my friend Deepan Gupta went a shop to buy a laptop with features he needed. Seller showed him a lot of laptops having various distinct features like cost, speed, memory, color, design, brand etc. But he was worrying only about memory and speed as he only needed these two. Because of so many laptops he got confused. He was not able to select a laptop. So he decided to select a skyline set in terms of {memory, speed} which will make it easier for him to decide. Objects are said to be in skyline set such that no one object in set dominates other object of set and all the objects which are not in the set are dominated by at least one object in the set. No Object in the set is dominated by any other object (both set and not in set). One Object dominate other object if all the features of first objects are greater than or equal to second object's corresponding features, but there exists at least a feature that is strictly greater than second object's corresponding feature. No one object dominate other object it means object does not satisfy the dominance condition, So Skyline Set can have two different objects with both same features.

For example:
Laptop1 : memory : 100GB, Processor Speed : 700GHz
Laptop2 : memory : 200GB, Processor Speed : 500GHz
Laptop3 : memory : 50GB, Processor Speed : 100GHz
Laptop4: memory : 200GB, Processor Speed : 500GHz
{Laptop1, Laptop2, Laptop4} are in skyline set while Laptop3 is not.


If Still not understood 'SKYLINE', refer this link :: LINK

Given N number of laptops with {M[i], S[i]}. Your task is to select a skyline set and print {M[i], S[i]} in newline of all the objects in set with decreasing order of M[i] value. If two Objects have same M[i] value, then you can print them in any order. For exact output format, refer to given examples.

Constraints

1<=T<=50, 1<=N<=10^5, 1<=M[i], S[i]<=10^9.

Input

First line contains t, number of test cases. For each test case, first line contains N, number of laptops. After that each of next N lines contains {M[i],S[i]} data for ith laptop, M[i] is memory and S[i] is speed of processor of ith Laptop.

Output

For each test case first line contains K, number of Skyline objects in set, then each of next K lines contains {M[i], S[i]} data for ith laptop in decreasing order of M[i].

Example

Input:
2
3
100 700
200 500
50 100

4
200 500
100 1000
50 900
1000 50

Output:
2
200 500
100 700
3
1000 50
200 500
100 1000

HINT: Just follow the statement very carefully. Observe the examples.


hide comments
cjn2007: 2022-02-09 07:01:08

Check if your skyline set is multi.

totallynotan: 2018-04-10 05:56:34

Why does this problem have such a tight time limit? Really hard (if not impossible) to pass in java even though solution is NlogN :(

anonymous: 2016-06-09 17:16:14

For similar challenge in three dimensions try NICEDAY problem.

pbd: 2016-02-23 20:47:34

getting TLE at case 4 (sub. id. 16349580 ). Used sets to take inputs
and to process output. used algo as given in link
by the author.

Last edit: 2016-02-23 20:48:40
yash : 2015-10-02 08:41:44

getting WA don't know whats the problem
submission id 15270384

Last edit: 2015-10-02 09:20:52
SHRINIKET ACHARYA: 2015-07-25 20:32:44

@author
getting WA id=14746924

vagesh_verma: 2015-07-11 21:39:57

@sir please look my solution ,,,,,id 14649920....it is correct still i m getting wrong answers.

Last edit: 2015-07-11 22:03:51
Ashwini: 2014-06-26 00:45:29

@author- thanks for replying. but in the example you have written {Laptop1, Laptop2, Laptop4} are in skyline set while Laptop3 is not.

if 2 and 4 can be in same set so for your replied example both can be in same set. right????

REply(rishav) : ignore my previous comment. you were right.
your op is incorrect.

i/p :
1
3
100 93
93 93
90 93

O/P should be

1
100 93.

in somecases you are printing all the pairs. check once.

Last edit: 2014-05-28 13:24:46
Ashwini: 2014-06-26 00:45:29

@author--
can you check why i'm getting wrong answer
submission id 11619294
solution of this problem seems pretty easy though

Last edit: 2014-05-28 13:18:11
xyz: 2014-06-26 00:45:29

easy one ... nice indeed....!


Added by:Rishav Goyal
Date:2014-03-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own