JOI 2008 Representative Selection - Ngày 3

Bạn làm một bức tranh dán giấy để trưng bày tại lễ hội trường JOI. Khi các tờ giấy chồng lên nhau, tranh sẽ dày và dễ bong. Bạn muốn biết số lớp giấy lớn nhất và tổng diện tích của phần có đúng số lớp đó.

Tấm nền là hình chữ nhật rộng \(a\) cm, cao \(b\) cm, được chia thành \(a\cdot b\) ô vuông cạnh \(1\) cm. Ô \((x,y)\) nằm ở cột thứ \(x\) từ trái sang và hàng thứ \(y\) từ dưới lên.

Bạn dán \(n\) tờ giấy hình chữ nhật. Cách dán một tờ được mô tả bằng \((p,q,r,s)\), với \(1 \le p \le r \le a\) và \(1 \le q \le s \le b\): tờ giấy phủ tất cả các ô từ cột \(p\) đến \(r\), hàng \(q\) đến \(s\), kể cả hai đầu. Kích thước tờ giấy là \((r-p+1)\times(s-q+1)\) cm.

Hãy tính số lớp giấy lớn nhất ở một vị trí và tổng diện tích có số lớp đó, không tính tấm nền là một lớp. Dữ liệu bảo đảm có ít nhất một ô được phủ bởi từ hai tờ giấy trở lên.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(n\), với \(1 \le n \le 5000\).

Dòng thứ hai chứa \(a,b\), với \(1 \le a,b \le 1000000\).

\(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(p_i,q_i,r_i,s_i\), thỏa mãn

Như vậy mỗi cạnh của một tờ giấy dài không quá \(20\) cm.

Dữ liệu ra

Ghi ra đầu ra chuẩn hai dòng. Dòng đầu chứa số lớp giấy lớn nhất. Dòng thứ hai chứa một số nguyên dương là tổng diện tích có số lớp giấy lớn nhất, tính bằng cm².

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(20\%\) dữ liệu có \(n \le 20\), \(1 \le a,b \le 50\); một phần \(20\%\) khác có \(n \le 100\).

Ví dụ

4
8 6
2 4 3 6
5 1 6 6
2 5 8 5
1 2 5 3

2
6

Chủ tịch M của JOI mỗi ngày đều cầu nguyện trước ảnh kim tự tháp, mong các thí sinh Nhật Bản đạt thành tích tốt tại IOI 2008. Một đêm, tượng Nhân sư xuất hiện trong giấc mơ và hứa thực hiện điều ước nếu được dâng một thỏi vàng có khối lượng thích hợp.

Khối lượng thỏi vàng phải dương và nhỏ hơn \(1\) kg. Khi viết theo đơn vị kg, nó phải bằng phân số nhỏ thứ \(k\) trong tập các giá trị phân số dương nhỏ hơn \(1\) có mẫu số không quá \(M\). Các phân số bằng nhau chỉ được tính một lần. Thỏi vàng nhẹ hơn hoặc nặng hơn đều không được chấp nhận.

Hãy tìm phân số đó, hoặc xác định rằng nó không tồn tại.

Dữ liệu vào

Đọc từ đầu vào chuẩn gồm một dòng chứa hai số nguyên dương \(M,k\), với \(M \le 30000\), \(k \le 200000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng. Nếu tồn tại phân số cần tìm, ghi tử số và mẫu số của dạng tối giản, cách nhau bởi dấu cách. Nếu không tồn tại, ghi \(-1\).

Chấm điểm

Giới hạn thời gian: \(0.5\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(5\) nhóm dữ liệu, mỗi nhóm \(20\) điểm; tổng cộng \(100\) điểm. Chỉ nhận điểm của một nhóm nếu chương trình trả lời đúng tất cả các bộ dữ liệu trong nhóm đó.

Ví dụ

6 8

2 3

6 12

-1

Trung tâm Y là một khu tập huấn rộng lớn, được nhiều người sử dụng cho sinh hoạt câu lạc bộ, trại huấn luyện, hòa nhạc và đào tạo. Khuôn viên là hình chữ nhật rộng \(w\), cao \(h\), có góc dưới trái \((0,0)\) và góc trên phải \((w,h)\).

Có \(b\) tòa nhà hình chữ nhật với các cạnh song song trục tọa độ. Tòa nhà thứ \(i\) có góc dưới trái \((s_i,t_i)\) và góc trên phải \((u_i,v_i)\). Các tòa nhà không chồng lấn. Biên không thuộc phần bên trong tòa nhà: được đi dọc theo biên, và ngay cả khi hai tòa nhà chạm nhau vẫn có khe đi qua giữa chúng.

Có \(a\) bảo vệ tại các vị trí \((x_1,y_1),\ldots,(x_a,y_a)\) ngoài các tòa nhà. Mỗi khi phát hiện một vật khả nghi, tất cả bảo vệ được thông báo và người có quãng đường ngắn nhất đến vật đó sẽ đi kiểm tra. Bảo vệ đi theo đường ngắn nhất trong khuôn viên và không đi xuyên qua bên trong tòa nhà vì chúng bị khóa vào ban đêm. Sau khi kiểm tra, người đó quay lại vị trí ban đầu theo cùng đường đi. Mỗi sự việc tiếp theo được xử lý tương tự.

Trong đêm có \(c\) vật khả nghi được phát hiện ngoài các tòa nhà. Biết tọa độ của chúng theo thứ tự phát hiện, hãy tính tổng quãng đường các bảo vệ đã đi, bao gồm cả lượt đi và lượt về. Khoảng cách được đo theo hình học Euclid.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(a,b,c\), với \(1 \le a \le 10\), \(1 \le b \le 50\), \(1 \le c \le 10\).

Dòng thứ hai chứa \(w,h\), với \(1 \le w,h \le 1000\).

\(a\) dòng tiếp theo chứa tọa độ nguyên \(x_i,y_i\) của các bảo vệ, với \(0 \le x_i \le w\), \(0 \le y_i \le h\).

\(b\) dòng tiếp theo chứa \(s_j,t_j,u_j,v_j\) của các tòa nhà, với \(0 \le s_j < u_j \le w\), \(0 \le t_j < v_j \le h\).

\(c\) dòng cuối chứa tọa độ nguyên \(p_k,q_k\) của các vật khả nghi theo thứ tự phát hiện, với \(0 \le p_k \le w\), \(0 \le q_k \le h\).

Dữ liệu ra

Ghi ra đầu ra chuẩn tổng quãng đường với ba chữ số sau dấu thập phân. Sai số không được vượt quá \(0.001\).

Chấm điểm

Giới hạn thời gian: \(5\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm; tổng cộng \(100\) điểm.

Ví dụ

2 4 3
8 6
3 0
8 0
2 1 3 3
3 2 5 4
5 1 6 2
6 4 7 5
4 5
6 4
1 5

30.847