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


Submit solution

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

Author:
Problem type

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


  • 2
    galiomid123456  commented on Aug. 24, 2020, 8:29 a.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, 8:04 a.m.

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


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

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