VM 11 Bài 04 - Sắp xếp đội hình

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem source:
VNOI Marathon 2011 - Tác giả: Lê Đôn Khuê
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

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 ở ~\left(0, 0\right)~ góc phải trên ở ~\left(120, 90\right)~. 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.

Giới hạn

Điểm được cho theo độ tốt của đáp án; cụ thể như sau:

Gọi tỉ lệ diện tích mặt sân bóng mà đội tuyển Anh kiểm soát là ~P~ ~(0 < P < 1)~.

  • Nếu ~P \leq 0.5~, bạn sẽ không được điểm cho test đó.
  • Nếu ~P \geq 0.75~, bạn sẽ được toàn bộ số điểm cho test đó.
  • Nếu ~50\% < P < 75\%~, bạn sẽ được ~\left(25 + 1200 \left(P - 0.5\right)^{2} \right)\%~ điểm cho test đó.

Sample Input

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11

Sample Output

12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21 
22 22

Note

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~.

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.