Ranh giới công trình
Đề bài
Mô tả
Bash đang phát triển một trò chơi xây dựng thành phố trực tuyến. Bản đồ là mặt phẳng tọa độ Descartes với tòa tháp được đặt trên đó. Tòa tháp thứ nằm tại điểm .
Trong trò chơi, người chơi lần lượt xây bức tường. Bức tường thứ là một đoạn thẳng nối tòa tháp và tòa tháp . Các bức tường được xây sao cho:
- hai bức tường không bao giờ cắt nhau, ngoại trừ có thể tại một đầu mút chung;
- một bức tường không đi qua tòa tháp nào khác ngoài hai đầu mút của nó;
- không có tòa tháp nào nằm hoàn toàn bên trong (không tính biên) một đa giác có các cạnh là các bức tường.
Một miền liên thông trên mặt phẳng được gọi là được bao phủ nếu mọi điểm bên trong miền đó cũng nằm bên trong một đa giác có các cạnh là các bức tường đã được xây. Một miền tối đại là một miền liên thông được bao phủ và không bị chứa thực sự trong một miền liên thông được bao phủ nào khác.
Để cho người chơi thấy tiến độ của mình, trò chơi cần hiển thị tổng diện tích của tất cả các miền tối đại sau mỗi lần xây một bức tường. Hãy giúp Bash tính các giá trị này.
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
- Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên và (; ): số tòa tháp và số bức tường.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và (): tọa độ của tòa tháp thứ . Các tòa tháp nằm ở các điểm phân biệt.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và (; ): hai tòa tháp được nối bởi bức tường thứ , theo thứ tự các bức tường được xây. Không có hai bức tường nào nối cùng một cặp tòa tháp. Các bức tường thỏa mãn các điều kiện trong đề bài.
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng gồm số nguyên. Số thứ là hai lần tổng diện tích của tất cả các miền tối đại sau khi bức tường đầu tiên được xây. Có thể chứng minh rằng giá trị này luôn là số nguyên.
Ràng buộc
- .
- ; .
- ; các tòa tháp nằm ở các điểm phân biệt.
- ; ; không có hai bức tường nối cùng một cặp tòa tháp; các bức tường thỏa mãn ba điều kiện trong đề bài.
- Tổng qua tất cả các bộ dữ liệu không vượt quá ; tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 7 0 0 2 0 2 2 0 2 4 0 1 2 2 3 3 4 4 1 1 3 2 5 5 3 3 3 0 0 3 0 0 3 1 2 2 3 3 1 |
0 0 0 8 8 8 12 0 0 9 |
Bộ thứ nhất: sau 4 bức tường đầu tiên, các tòa tháp 1, 2, 3, 4 tạo thành hình vuông diện tích , nên đáp án là . Bức tường thứ 5 là đường chéo của hình vuông, không làm thay đổi miền được bao phủ tối đại. Bức tường thứ 6 không tạo ra đa giác mới nào. Bức tường thứ 7 tạo thành một tam giác mới với các tòa tháp 2, 5, 3, diện tích . Tổng diện tích được bao phủ tối đại là , nên đáp án là . Bộ thứ hai: sau bức tường cuối cùng, miền được bao phủ tối đại là một tam giác diện tích , nên đáp án là . |
| 2 4 5 0 0 4 0 4 4 0 4 1 3 1 2 2 3 3 4 4 1 3 2 0 0 1 5 2 0 1 2 2 3 |
0 0 16 16 32 0 0 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: đường chéo 1-3 được xây trước; bức tường thứ 3 khép kín tam giác 1, 2, 3 diện tích ; bức tường thứ 5 khép kín tam giác 1, 3, 4, cả hình vuông diện tích được bao phủ. Bộ thứ hai: hai bức tường không tạo ra đa giác nào. |
Bình luận