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:
20220209 07:01:08
Check if your skyline set is multi. 

totallynotan:
20180410 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:
20160609 17:16:14
For similar challenge in three dimensions try NICEDAY problem. 

pbd:
20160223 20:47:34
getting TLE at case 4 (sub. id. 16349580 ). Used sets to take inputs


yash :
20151002 08:41:44
getting WA don't know whats the problem


SHRINIKET ACHARYA:
20150725 20:32:44
@author


vagesh_verma:
20150711 21:39:57
@sir please look my solution ,,,,,id 14649920....it is correct still i m getting wrong answers. Last edit: 20150711 22:03:51 

Vijay:
20150529 10:20:07
Last edit: 20150530 20:00:57 

Ashwini:
20140626 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.


Ashwini:
20140626 00:45:29
@author

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