trang chủ / đề bài / icpc26_mt_f

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ó n điểm quan sát, mỗi điểm quan sát là một điểm.
  • Có m 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ó q 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 t (1≤t≤104): số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng như sau:

  • Dòng đầu tiên chứa ba số nguyên n, m và q (1≤n,m,q≤105): số điểm quan sát, số hình chữ nhật và số hình tròn.
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên x,y (0≤x,y≤108): một điểm quan sát tại tọa độ (x,y).
  • m dòng tiếp theo, mỗi dòng chứa bốn số nguyên x1,y1,x2,y2 (0≤x1,y1,x2,y2≤108, x1<x2, y1<y2): một tòa nhà hình chữ nhật có góc dưới trái là (x1,y1) và góc trên phải là (x2,y2).
  • q dòng tiếp theo, mỗi dòng chứa ba số nguyên x,y,r (0≤x,y,r≤108): một khu bảo tồn hình tròn có tâm (x,y) và bán kính r.

Dữ liệu đảm bảo tổng các giá trị n, tổng các giá trị m và tổng các giá trị q trên mọi bộ dữ liệu đều không vượt quá 105.

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

  • 1≤t≤104.
  • 1≤n,m,q≤105; tổng n, tổng m, tổng q trên mọi bộ dữ liệu đều không vượt quá 105.
  • 0≤x,y≤108 với mọi điểm quan sát.
  • 0≤x1,y1,x2,y2≤108, x1<x2, y1<y2 với mọi hình chữ nhật.
  • 0≤x,y,r≤108 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ừ x=1 (hình chữ nhật thứ nhất và hình tròn tâm (3,5) bán kính 2) đến x=8 (điểm (8,4), hình chữ nhật thứ hai, hình tròn tâm (7,2)), và từ y=0 (hình chữ nhật thứ hai) đến y=7 (điểm (5,7) và hình tròn tâm (3,5)). Hình vuông nhỏ nhất là [1,8]×[0,7], diện tích 72=49. Bộ thứ hai: hình vuông [4,6]×[4,6], diện tích 4. Bộ thứ ba: các đối tượng trải từ x=1 đến x=5 và từ y=2 đến y=6, diện tích 42=16.
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ừ x=0 đến x=14 và từ y=0 đến y=10; cạnh hình vuông phải ít nhất là 14, diện tích 196. Bộ thứ hai: hình tròn tâm (0,108) bán kính 108 trải từ x=−108 đến x=108, 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à 2·108, diện tích 4·1016. Ví dụ này được bổ sung, không có trong đề gốc.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0