← 返回题目列表

AtCoder · past23_e

E. 对分数进行排序

中文机器翻译题面 查看原题

问题陈述

给定一系列 N 成对不同的不可约分数 \displaystyle \left(\frac{A_1}{B_1}, \frac{A_2}{B_2}, \dots, \frac{A_N}{B_N}\right),按升序排序。

约束

  • 1 \leq N \leq 10^3
  • 1 \leq A_i \leq 10^{18}
  • 1 \leq B_i \leq 10^{18}
  • \gcd(A_i, B_i) = 1
  • (A_i,B_i) \neq (A_j,B_j) if i \neq j.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

如果结果序列是 \displaystyle \left(\frac{C_1}{D_1}, \frac{C_2}{D_2}, \dots, \frac{C_N}{D_N} \right),按以下格式打印。

C_1 D_1
C_2 D_2
\vdots
C_N D_N

示例输入 1

3
2 3
1 2
3 5

示例输出 1

1 2
3 5
2 3

自从 \displaystyle \frac{1}{2} \lt \frac{3}{5} \lt \frac{2}{3},排序后的序列为 \displaystyle \left(\frac{1}{2}, \frac{3}{5}, \frac{2}{3} \right).


示例输入 2

5
1 5
1 7
6 5
9 8
9 4

示例输出 2

1 7
1 5
9 8
6 5
9 4

示例输入 3

10
39 83
93 70
5 92
81 67
30 53
57 5
91 58
21 85
81 34
37 38

示例输出 3

5 92
21 85
39 83
30 53
37 38
81 67
93 70
91 58
81 34
57 5