Khu quan sát
Đề bài
Mô tả
Một nhóm nghiên cứu dự định xây dựng một khu quan sát lớn trên mặt phẳng tọa độ. Khu quan sát phải là một hình vuông có các cạnh song song với các trục tọa độ.
Trên bản đồ đã có sẵn một số đối tượng:
- Có điểm quan sát, mỗi điểm quan sát là một điểm.
- Có tòa nhà, mỗi tòa nhà là một hình chữ nhật có các cạnh song song với các trục tọa độ.
- Có khu bảo tồn, mỗi khu bảo tồn là một hình tròn.
Khu quan sát phải chứa trọn vẹn mọi đối tượng trên bản đồ. Nói cách khác, mọi điểm, mọi hình chữ nhật và mọi hình tròn đều phải nằm hoàn toàn bên trong hình vuông.
Yêu cầu: Hãy xác định diện tích nhỏ nhất có thể của khu quan sát.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên (): số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng như sau:
- Dòng đầu tiên chứa ba số nguyên , và (): số điểm quan sát, số hình chữ nhật và số hình tròn.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên (): một điểm quan sát tại tọa độ .
- dòng tiếp theo, mỗi dòng chứa bốn số nguyên (, , ): một tòa nhà hình chữ nhật có góc dưới trái là và góc trên phải là .
- dòng tiếp theo, mỗi dòng chứa ba số nguyên (): một khu bảo tồn hình tròn có tâm và bán kính .
Dữ liệu đảm bảo tổng các giá trị , tổng các giá trị và tổng các giá trị trên mọi bộ dữ liệu đều không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên trên một dòng: diện tích nhỏ nhất có thể của một hình vuông có các cạnh song song với các trục tọa độ và chứa trọn vẹn mọi đối tượng đã cho.
Ràng buộc
- .
- ; tổng , tổng , tổng trên mọi bộ dữ liệu đều không vượt quá .
- với mọi điểm quan sát.
- , , với mọi hình chữ nhật.
- với mọi hình tròn.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 2 2 8 4 5 7 1 1 5 3 3 0 8 5 3 5 2 7 2 1 1 1 1 5 5 4 4 6 6 5 5 1 1 1 1 3 6 1 2 5 6 3 4 1 |
49 4 16 |
Bộ thứ nhất: các đối tượng trải từ (hình chữ nhật thứ nhất và hình tròn tâm bán kính ) đến (điểm , hình chữ nhật thứ hai, hình tròn tâm ), và từ (hình chữ nhật thứ hai) đến (điểm và hình tròn tâm ). Hình vuông nhỏ nhất là , diện tích . Bộ thứ hai: hình vuông , diện tích . Bộ thứ ba: các đối tượng trải từ đến và từ đến , diện tích . |
| 2 1 1 1 10 10 12 3 14 9 2 2 2 1 1 1 100000000 0 0 0 1 1 0 100000000 100000000 |
196 40000000000000000 |
Bộ thứ nhất: các đối tượng trải từ đến và từ đến ; cạnh hình vuông phải ít nhất là , diện tích . Bộ thứ hai: hình tròn tâm bán kính trải từ đến , nên hình vuông có thể (và phải) vượt ra ngoài vùng tọa độ không âm; cạnh nhỏ nhất là , diện tích . Ví dụ này được bổ sung, không có trong đề gốc. |
Bình luận