Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Time Limit: 5000MSMemory Limit: 131072K
Total Submissions: 1043Accepted: 236


Xiao Feng is a big fan of the online multiplayer racing game PopKart. Among various types of play, Xiao Feng prefers the Speed Game, in which players compete to be the fastest racer. In order to win the races, apart from solid driving skills, the player must also own a top-class kart. Results of races among experienced players are mostly decided by the karts which they ride.

Now a new generation of karts has hit the market. Xiao Feng wants to purchase one of them. Two factors prevents him from going straightly for the best ones. First, the available (virtual) funds are limited. Second and more importantly, it is a non-trivial task to decide which karts are the best.

To find out the best karts that he can afford, Xiao Feng employs a simple scheme to classify the karts by their performance.

The performance of a kart is characterized by two parameters—the straight-line speed v and the drift speed w. A kart is said to be superior to another if and only if it is superior in either speed and not inferior in the other. All karts to which no other karts are superior are classified as karts of class 1. For each m ≥ 2, all karts to which only karts of classes 1 through m − 1 are superior are classified as karts of class m.

Given the straight-line and drift speeds of n karts, classify them as specified above.


The input contains a single test case. The first line contains n (1 ≤ n ≤ 105). The remaining n lines each contain two integers v and w (0 ≤ v, w < 106), the straight-line and drift speeds of a kart.


For each class in increasing order of m, print a list of karts of that class using the format

k: (v1,w1) (v2,w2) (vk,wk)

where k is the number of karts of that class, and (v1, w1), (v2, w2), …, (vk, wk) are their straight-line and drift speeds. The k pairs of speeds shall be sorted so that vi < vj ∨ (vi = vjwiwj) for any 1 ≤ i < jk (“∨” and “∧” represent logical OR and AND, respectively).

Sample Input

1 2
2 1
2 3
3 2

Sample Output

2: (2,3) (3,2)
2: (1,2) (2,1)


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator