Sắp xếp chèn (INSERTION SORT)


Submit solution

Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho một dãy điểm gồm n điểm trên tọa độ tích Đề-Các vuông góc nguyên hai chiều \(A_1(x_1,y_1),A_2(x_2,y_2),...A_n(x_n,y_n)\) sao cho 2 điểm bất kỳ không cùng tung độ hoặc hoành độ.

Bạn hãy lập trình thuật toán sắp xếp chèn nhưng khi đã sắp được sắp \(\left\lfloor n/2 \right\rfloor \) số điểm theo hoành độ tăng dần rồi thì dừng và xuất ra dãy điểm ở dòng thứ nhất và sau đó sắp xếp dãy mới này theo tung độ giảm dần khi đã sắp được \(\left\lfloor n/2 \right\rfloor \) số điểm rồi thì dừng xuất ra dãy điểm ở hàng thứ 2.

Sắp xếp chèn

Input

Dòng đầu là số nguyên dương n là số điểm \((5<=n<=100)\)

n dòng tiếp theo mỗi dòng chứa 2 số nguyên có trị tuyệt đối nhỏ hơn \(30000\) và không có bất kỳ hai điểm nào có cùng tung độ hoặc hoành độ

Output

Dòng đầu chứa n điểm sau khi sắp xếp chèn tăng dần theo hoành độ được các điểm từ 1 đến hết thứ \(\left\lfloor n/2 \right\rfloor \) (xem ví dụ)

Dòng thứ hai chứa n điểm sau khi sắp xếp chèn giảm dần theo tung độ được các điểm từ 1 đến hết thứ \(\left\lfloor n/2 \right\rfloor \) (xem ví dụ)

Ví dụ

Input

5
7 5
2 4
0 1
8 3
6 8

Output

(2,4) (7,5) (0,1) (8,3) (6,8) 
(7,5) (2,4) (0,1) (8,3) (6,8)

Giải thích : có 5 điểm ta chỉ sắp \(\left\lfloor 5/2 \right\rfloor =2\) điểm đầu dòng một là theo hoành độ tăng dần, dòng hai là theo tung độ giảm dần


Comments


  • 3
    galiomid123456  commented on Aug. 24, 2020, 12:29 p.m. edited

    Admin có thể thêm nhiều bài toán về sắp xếp đc k ạ :3


  • 2
    TICHPX  commented on Aug. 24, 2020, 12:04 p.m.

    Chả có nhẽ học sang cout phải dùng cout


  • 2
    Tan_CNTT3_K60  commented on Aug. 24, 2020, 11:48 a.m.

    Ngồi fix cả buổi k biết sai ở đâu, chuyển printf thành cout thì accept :)