VO 19 Bài 1 - Sữa tươi trân châu đường hổ


Submit solution

Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Tháng ~7~ 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; TocoToco quyết định mở hàng loạt những chinh nhánh mới trên khắp thành phố Hà Nội. TocoToco muốn tập trung vào các trường học – khu vực có lượng khách hàng tiềm năng cao. Đặc biệt TocoToco còn xây dựng riêng một cơ sở chuyên sản xuất nguyên liệu để cung ứng với số lượng lớn.

Bản đồ Hà Nội được vẽ trên mặt phẳng toạ độ Descartes (Oxy). Khu vực nội đô là hình vuông với hai góc đối diện là ~(0~, ~0)~ và ~(10^{9}~, ~10^{9})~. Toàn thành phố có ~N~ trường học, mỗi trường chiếm một khu hình chữ nhật có các cạnh song song với một trong hai trục toạ độ. Khuôn viên của các trường có thể giáp nhau hoặc giao nhau.

Tocotoco được ~N~ trường cho phép mở cửa hàng trong khuôn viên của họ. Do đó, TocoToco sẽ mở ~N~ cửa hàng trà sữa, cửa hàng thứ ~i~ đặt tại một điểm nằm trong (hoặc trên biên) của trường thứ ~i~. Đồng thời TocoToco sẽ mở thêm một xưởng chế biến nguyên liệu phục vụ các chi nhánh, cơ sở chế biến này có thể nằm ở bất kì đâu trong nội đô (có thể nằm ngoài hoặc trong một trường nào đó, có thể cùng vị trí với một cửa hàng).

Để việc vận chuyển nguyên liệu được thuận lợi, TocoToco muốn tổng khoảng cách Manhattan từ xưởng chế biến tới ~N~ cửa hàng là nhỏ nhất. ~N~ cửa hàng trà sữa không bắt buộc phải đặt ở ~N~ điểm phân biệt.

TocoToco treo giải thưởng ~998244353~ 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 ~9~, Nhi chưa thể giải được bài này. Các bạn hãy giúp Nhi nhé.

Nhắc lại: Khoảng cách Manhattan giữa hai điểm có toạ độ ~(x_1~, ~y_1)~ và ~(x_2~, ~y_2)~ là: ~|x_1 - x_2| + |y_1 - y_2|~

Input

  • Dòng đầu tiên ghi số nguyên ~N~ ~(1 \leq N \leq 105)~ – Số trường học trong thành phố.
  • ~N~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên ~x_1~ ~y_1~ ~x_2~ ~y_2~ ~(0 \leq x_1~, ~y_1~, ~x_2~, ~y_2 \leq 10^{9})~ thể hiện khuôn viên của trường thứ ~i~ là hình chữ nhật có hai góc đối diện với toạ độ ~(x_1~, ~y_1)~ và ~(x_2~, ~y_2)~.

    Output

  • Dòng đầu tiên ghi một số nguyên duy nhất: Tổng khoảng cách Manhattan nhỏ nhất từ xưởng chế biến nguyên liệu tới ~N~ cửa hàng.

  • Dòng thứ hai ghi hai số nguyên ~x_c y_c~ ~(0 \leq x_c, y_c \leq 10^{9})~ – vị trí đặt xưởng chế biến. ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~x~ ~y~ ~(0 \leq x~, ~y \leq 10^{9})~ – vị trí đặt cửa hàng thứ ~i~.

Nếu có nhiều đáp án tối ưu, bạn có thể in ra phương án bất kì.

Giới hạn

  • Subtask ~1~ ~(11/70~ điểm): ~N \leq 1000~
  • Subtask ~2~ ~(12/70~ điểm): ~x_1 = x_2~, ~y_1 = y_2~ với mọi trường học.
  • Subtask ~3~ ~(13/70~ điểm): ~x_1 = x_2 = 0~ với mọi trường học.
  • Subtask ~4~ ~(34/70~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

3
0 0 1 2
4 1 7 4
1 3 3 4

Sample Output 1

4
3 2
1 2
4 2
3 3

Sample Input 2

3
2 2 3 4
1 1 4 3
3 0 5 2

Sample Output 2

0
3 2
3 2
3 2
3 2

Comments

There are no comments at the moment.