STRATEGY - Sắp xếp đội hình
Giới hạn- Thời gian: 0.4s
- 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.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274709/problem/F
https://codeforces.com/group/FLVn1Sc504/contest/272672/problem/D
Sau thất bại của đội tuyển Anh tại World Cup 2010, huấn luyện viên Fabio Capello quyết định sẽ áp dụng một công nghệ mới cho đội tuyển Anh tại Euro 2012. Ông giao nhiệm vụ cho HLV phó thu thập thông tin về vị trí trên sân của các cầu thủ đối phương và sẽ sắp xếp cầu thủ của mình sao cho diện tích mặt sân mình kiểm soát là nhiều nhất có thể.
Sân bóng là một hình chữ nhật có góc trái dưới ở (0, 0) góc phải trên ở (120, 90). Bạn hãy sắp xếp 11 cầu thủ của đội tuyển Anh sao cho các vị trí này không trùng với các vị trí của đối phương và diện tích sân mà đội tuyển Anh kiểm soát là lớn nhất có thể. Một vị trí trên sân sẽ được kiểm soát bởi đội nào có cầu thủ ở gần vị trí đó hơn.
Input
Dữ liệu vào ghi 11 dòng, mỗi dòng ghi 2 số x y nguyên là vị trí của cầu thủ đối phương
Output
Dữ liệu ra ghi 11 dòng, mỗi dòng là 2 số nguyên x y là vị trí của cầu thủ đội tuyển Anh.
Điểm được cho theo độ tốt của đáp án.
Example
Input:1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
Output:12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
Giải thích: đối phương chiếm được phần phía dưới đường chéo có diện tích là 264.5. Đội tuyển Anh chiếm được phần phía trên đường chéo có diện tích là 10535.5.
Lưu ý : Trong lúc thi, BTC sẽ chấm trước 40% số test, điểm tối đa các bạn submit đúng cả 40% số test sẽ là 40 điểm.
- Người up: voj
- Nguồn bài: VNOI Marathon 2011 - Tác giả: Lê Đôn Khuê