VMCOINS - Trò chơi với những đồng xu

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

RR có N đồng xu giống hệt nhau.

RR đặt N đồng xu lên mặt phẳng tọa độ Oxy, đồng xu thứ i có tọa độ (xi, yi). Không có 2 đồng xu nào cùng vị trí.

Hai đồng xu ở vị trí (x1, y1) và (x2, y2) được gọi là kề nhau nếu |x1 - x2| + |y1 - y2| = 1.

Một cách đặt các đồng xu lên mặt phẳng tọa độ như vậy được gọi là một trạng thái của N đồng xu.

Xét 2 trạng thái: H1, với các đồng xu ở tọa độ (x1, y1), (x2, y2)..., (xN, yN) và H2 với các đồng xu ở tọa độ (u1, v1), (u2, v2), ...., (uN, vN).

Hai trạng thái H1 và H2 được gọi là tương đương nếu: tồn tại một hoán vị (P1, P2, ..., PN) thỏa mãn:

  • u1 - x(P1) = u2 - x(P2) = ... = uN - x(PN)
  • v1 - y(P1) = v2 - y(P2) = ... = vN - y(PN).

Nhiệm vụ của bạn là chuyển các đồng xu từ trạng thái xuất phát đến trạng thái đích (hoặc một trạng thái tương đương với trạng thái đích), sau không quá 10 6 bước.

Mỗi bước, bạn được di chuyển đúng một đồng xu, từ vị trí A đến vị trí B, nếu:

  • Vị trí B không có đồng xu nào
  • Sau khi đặt đồng xu vào vị trí B, nó kề với ít nhất 2 đồng xu khác.

Cho biết rằng luôn tồn tại dãy di chuyển thỏa mãn đề bài, và tồn tại 2 đồng xu trong trạng thái xuất phát sao cho nếu di chuyển 2 đồng xu này đến vị trí bất kỳ (không trùng nhau và không trùng với các đồng xu khác), thì vẫn tồn tại kết quả.

Input

  • Dòng 1: Chứa số nguyên dương N
  • Dòng 2..N+1: Mỗi dòng 2 số nguyên xi, yi, là tọa độ của đồng xu thứ i trong trạng thái xuất phát
  • Dòng N+2: Dòng trống
  • Dòng N+3..2*N+2: Mỗi dòng 2 số nguyên xi, yi, là tọa độ của đồng xu thứ i trong trạng thái đích.

Output

Dòng 1: K - số bước di chuyển của bạn

K dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương xi, yi, ui, vi, thể hiện bạn di chuyển đồng xu từ (xi, yi) đến (ui, vi).

Nếu có nhiều cách di chuyển thỏa mãn, bạn chỉ cần in ra cách di chuyển bất kỳ (không cần gồm ít bước nhất).

Giới hạn

  • 1 ≤ N ≤ 30;
  • xi, yi là các số nguyên có giá trị tuyệt đối không quá 10 9 ;

Chấm điểm

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ được chấm với 20% số test của BTC (không gồm test ví dụ). Điểm tối đa mà bạn có thể nhận được là 100.

Với mỗi test, bài của bạn sẽ được chấm là đúng nếu các bước di chuyển của bạn hợp lệ và sau khi thực hiện K bước di chuyển, trạng thái thu được tương đương với trạng thái kết thúc

Example 

Input:
5
1 1
1 2
2 2
2 3
3 2

1 2
1 3
2 1
2 2
2 3

Output:
2
3 2 2 1
1 1 1 3

  • Người up: voj
  • Nguồn bài: VM13 - Nguyễn Thành Trung