trang chủ / đề bài / icpcwf14_c

Cân bằng cần cẩu

Đề bài

Mô tả

Ở đâu có công trình xây dựng lớn, ở đó có những chiếc cần cẩu làm công việc nâng hạ. Hiếm ai nghĩ tới việc cần cẩu là những ví dụ tuyệt vời của kỹ thuật: một kết cấu có trọng lượng (tương đối) nhỏ nhưng nâng được những vật nặng hơn nhiều. Tuy vậy, ngay cả những chiếc cần cẩu được chế tạo tốt nhất cũng có giới hạn về khối lượng mà chúng nâng được.

Hiệp hội các nhà sản xuất cần cẩu (ACM) cần một chương trình tính khoảng khối lượng mà một cần cẩu có thể nâng. Vì cần cẩu có tính đối xứng, các kỹ sư của ACM quyết định chỉ xét một mặt cắt ngang của cần cẩu, có thể xem như một đa giác đặt trên trục x.

Hình: mặt cắt ngang của cần cẩu trong ví dụ thứ nhất. Mũi tên chỉ đỉnh treo vật nặng.

Hình trên là mặt cắt ngang của cần cẩu trong ví dụ thứ nhất. Giả sử mỗi ô 1×1 của mặt cắt ngang cần cẩu nặng 1 kilôgam (khối lượng phân bố đều, khối lượng cần cẩu bằng diện tích đa giác), và vật cần nâng được treo tại một đỉnh của đa giác (đỉnh mà mũi tên chỉ vào trong hình). Hãy viết chương trình xác định khoảng khối lượng vật nặng mà với nó cần cẩu không bị đổ sang trái hay sang phải.

Cần cẩu chỉ tựa lên mặt đất tại các đỉnh của đa giác nằm trên trục x. Cần cẩu không đổ khi và chỉ khi hoành độ trọng tâm chung của cần cẩu và vật nặng nằm trong đoạn từ hoành độ nhỏ nhất tới hoành độ lớn nhất của các điểm tựa đó (kể cả hai đầu mút).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n, số đỉnh của đa giác mô tả hình dạng cần cẩu.

n dòng tiếp theo, mỗi dòng chứa hai số nguyên xi, yi: tọa độ các đỉnh của đa giác theo thứ tự. Vật nặng được treo tại đỉnh đầu tiên của đa giác.

Dữ liệu ra

In ra khoảng khối lượng (tính bằng kilôgam) có thể treo vào cần cẩu mà cần cẩu không bị đổ. Nếu khoảng đó là [a,b], in ra ⌊a⌋ .. ⌈b⌉. Ví dụ, nếu khoảng là [1,5; 13,3], in ra 1 .. 14. Nếu khoảng là [a,∞), in ra ⌊a⌋ .. inf. Nếu cần cẩu không thể mang bất kỳ khối lượng nào, in ra unstable.

Ràng buộc

  • 3≤n≤100.
  • −2000≤xi≤2000, 0≤yi≤2000.
  • Đa giác là đa giác đơn, có ít nhất hai đỉnh nằm trên trục x.

Ví dụ

Input Output Giải thích
7
50 50
0 50
0 0
30 0
30 30
40 40
50 40
0 .. 1017 Đây là cần cẩu trong hình. Các điểm tựa là (0,0) và (30,0), vật treo tại (50,50).
7
50 50
0 50
0 0
10 0
10 30
20 40
50 40
unstable Các điểm tựa là (0,0) và (10,0): trọng tâm cần cẩu đã nằm bên phải x=10 ngay cả khi không treo gì, và treo thêm ở x=50 chỉ làm nó lệch phải thêm.

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