Tháng vừa qua, thương hiệu trà sữa TocoToco vừa cho ra mắt một loại đồ uống mới với tên gọi khá kì lạ “Tiger Sugar” – “Sữa tươi trân châu đường hổ. Đây được coi là một cú hích mạnh mẽ sau phong trào “Sữa tươi trân châu đường đen” mới nổi; hứa hẹn tạo ra một phong cách mới trong kho tàng cách pha chế trà sữa vốn đã rất phong phú.
Tiger Sugar là sự kết hợp đồng điệu của các thành phần: Sữa tươi thanh trùng, siro đường hổ và trân châu đen. Trong đó, "đường hổ" là cái tên được nhiều bạn trẻ quan tâm bởi sự lạ lẫm của nó. Thực ra, siro đường hổ là thành quả của quá trình cô đường nâu (loại đường quen thuộc trong dân gian) theo bí kíp rất riêng của TocoToco. Những giọt siro đường nâu chạy dọc thân cốc, tạo ra những đường vân đẹp mắt, mạnh mẽ như vân của loài hổ. (Nguồn: kênh 14)
Để quảng bá cho sản phẩm vô cùng độc và lạ này, vào năm ngoái, TocoToco quyết định mở hàng loạt những chi nhánh mới trên khắp thành phố Hà Nội. Bản đồ Hà Nội được vẽ trên mặt phẳng toạ độ Descartes 𝑂𝑥𝑦. Khu vực nội đô là hình vuông với hai góc đối diện có toạ độ là và . TocoToco đã mở cửa hàng, cửa hàng thứ nằm ở điểm có toạ
độ .
Tuy sản phẩm sữa tươi trân châu đường hổ đã đạt được thành công vang dội nhưng TocoToco lại không thu về lợi nhuận như mong muốn. Lí do là vì các cửa hàng được đặt cách quá xa nhau, khiến cho chi phí vận chuyển vô cùng lớn. Do đó, TocoToco muốn di dời 𝑛 cửa hàng này sao cho tổng khoảng cách Manhattan giữa mọi cặp cửa hàng là nhỏ nhất có thể. Tuy nhiên, để đảm bảo không làm phật lòng những khách hàng lâu năm, TocoToco sẽ di dời các cửa hàng sao cho tổng khoảng cách Manhattan giữa vị trí cửa hàng cũ và vị trí cửa hàng mới tương ứng không vượt quá .
TocoToco treo giải thưởng ly sữa tươi trân châu đường hổ miễn phí cho ai tìm ra vị trí tốt nhất để đặt xưởng chế biến và các cửa hàng. Là một fan cuồng của thúc uống này, Nhi muốn giải bài toán để được uống trà sữa miễn phí cả đời. Nhưng do mới học hết lớp , Nhi chưa thể giải được bài này. Các bạn hãy giúp Nhi nhé.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và là số cửa hàng TocoToco đang có và giới hạn tổng khoảng cách Manhattan giữa vị trí cũ và vị trí mới của cửa hàng này.
Trong dòng tiếp theo, dòng thứ chứa hai số nguyên và là toạ độ vị trí hiện tại của cửa hàng thứ .
Dữ liệu ra:
Dòng đầu tiên chứa một số nguyên là tổng khoảng cách Manhattan nhỏ nhất giữa mọi cặp cửa hàng sau khi di chuyển.
Trong dòng tiếp theo, dòng thứ chứa hai số nguyên thể hiện toạ độ vị trí của cửa hàng thứ sau khi di chuyển.
Nếu có nhiều phương án di chuyển tối ưu, bạn được phép in ra phương án bất kì.