Giáo trình DIVIDE ioicamp.net

Giáo trình DIVIDE ioicamp.net.Đề bài:
2 nước láng giềng AA và BB đang tranh chấp nhau một khu đất rất giàu tài nguyên. Khu
đất này có hình chữ nhật với kích thước m x n. Trong và trên biên khu đất này có 2k mỏ
than và 2h mỏ dầu. Sau nhiều năm chiến tranh mà không giải quyết được tranh chấp, 2
nước này quyết định ngồi vào bàn đàm phán để phân chia khu đất này làm 2 phần, mỗi
phần thuộc về một nước. Và hiệp định chỉ được ký kết nếu việc phân chia này đạt được
sự công bằng tuyệt đối.
Yêu cầu đặt ra là bạn hãy tìm cách phân chia khu đất thỏa mãn:
 Đường phân chia là một đường thẳng không đi qua một mỏ nào.
 2 phần của khu đất sau khi phân chia có diện tích bằng nhau.
 Mỗi phần của khu đất sau khi phân chia đều có k mỏ than và h mỏ dầu.
Để định vị các mỏ thì người ta sử dụng một hệ trục tọa độ với 2 trục Ox và Oy, chiều
dương của trục Ox trùng với cạnh có độ dài m, chiều dương của trục Oy trùng với cạnh có
độ dài n. Gốc O của trục tọa độ trùng với một góc vuông của khu đất. Khi đó mỗi mỏ sẽ
được biểu diễn bởi một cặp số nguyên là tọa độ của mỏ. Chú ý là tại một vị trí có thể có
nhiều hơn một mỏ thuộc một hoặc hai loại.

Input: DIVIDE.INP
 Dòng đầu tiên ghi 2 số nguyên m và n.
 Dòng tiếp theo ghi 2 số nguyên k và h.
 Trong 2k dòng tiếp theo, mỗi dòng ghi 2 số nguyên là tọa độ của một mỏ than.
 Trong 2h dòng cuối, mỗi dòng ghi 2 số nguyên là tọa độ của một mỏ dầu.
Output: DIVIDE.OUT
 Nếu tồn tại một phương án chia đất thỏa mãn yêu cầu:
+ Dòng thứ nhất ghi số 1.
+ Dòng thứ hai ghi 4 số thực x1, y1, x2, y2 với ý nghĩa là đường thẳng chia đất
đi qua 2 điểm có tọa độ (x1, y1) và (x2, y2) sao cho 2 điểm (x1, y1) và (x2, y2)
phải là 2 điểm nằm trên biên của khu đất.
 Nếu không tồn tại phương án chia đất thỏa mãn yêu cầu thì ghi ra duy nhất một
số –1.
2

Giới hạn:
 Kích thước và sai số:
+ 1 ≤ m, n ≤ 106
+ h, k ≤ 10000
+ Các số thực trong file Output được ghi với độ chính xác 5 chữ số sau dấu
phẩy.
 Thời gian: 0.5s/test
 Bộ nhớ: 1MB
 Bạn chỉ nhận được điểm của các test có kết quả là –1 khi đúng không ít hơn 50%
các test còn lại.
Ví dụ :
DIVIDE.INP DIVIDE.OUT
5 4
2 1
0 0
0 2
4 2
3 4
1 1
3 3
1
3.00000 0.00000 2.00000 4.00000